<!DOCTYPE html><html lang="en">
      
      
        
    
    
    
    

      
      
      <head>
        <meta charset="utf-8">
        <meta name="format-detection" content="telephone=no">  
        
        <title>Lecture 1: Introduction and Proofs | Video Lectures | Mathematics for Computer Science | Electrical Engineering and Computer Science | MIT OpenCourseWare</title>
    <!-- Begin Automatic Metadata Insertion -->
    <meta content="6-042j-mathematics-for-computer-science-fall-2010" name="WT.cg_n">
    <meta content="Lecture 1: Introduction and Proofs" name="WT.cg_s">
    <meta content="Introduction to mathematical proofs using axioms and propositions. Covers basics of truth tables and implications, as well as some famous hypotheses and conjectures." name="Description">
    <meta content="Leighton, Tom" name="Author">
    <meta content="Dijk, Marten van " name="Author">
    <meta content="6.042J,6.042,18.062J,18.062,proof,axiom,proposition,lemma,predicate,factoring,coloring,truth table,implication,Computer Science,Probability and Statistics,Applied Mathematics,Discrete Mathematics" name="keywords">
    <meta content="6.042J Mathematics for Computer Science | Lecture 1: Introduction and Proofs" name="Search_Display">
    <meta content="Computer Science" itemprop="about">
    <meta content="Probability and Statistics" itemprop="about">
    <meta content="Applied Mathematics" itemprop="about">
    <meta content="Discrete Mathematics" itemprop="about">
    <!-- End Automatic Metadata Insertion -->

	<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/grid.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/base.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/menu.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/jquery.bubblepopup.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/search.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/courses.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/courses_new.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/jquery.jscrollpane.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/media_tabs.css">
	<link href="../../../common/xml/ocwcc.rdf" type="application/rdf+xml" rel="metadata">
	<link rel="canonical" href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-1-introduction-and-proofs/">
	<link rel="apple-touch-icon" href="../../../common/images/apple-touch-icon.png">
	
	
      
	
	<script type="text/javascript" src="../../../common/scripts/jquery.js"></script>
	<script type="text/javascript" src="../../../common/scripts/ocw-media-utils-offline.js"></script>
	<script type="text/javascript" src="../../../common/scripts/ocw-offline.js"></script>
	<script type="text/javascript" src="../../../common/scripts/jquery.bubblepopup.min.js"></script>
	<script type="text/javascript" src="../../../common/scripts/jquery-ui.min.js"></script>
	<script type="text/javascript" src="../../../common/scripts/jquery.jscrollpane.min.js"></script>
	<script type="text/javascript" src="../../../common/scripts/expandy.js"></script>
	<script type="text/javascript" src="../../../common/scripts/bubble-popup-offline.js"></script>
	
	
	
    <script type="text/javascript">
      $(document).ready(function() {
        $("#tabs").tabs();
        IpadScroller();
      });
    </script>
    
    
    
    
    
    
      
       
		 

        
        
        

        
        
        
        
        
        
        
        
        
      </head>
    <body itemscope itemtype="http://schema.org/WebPage">
        
	

        <header id="top">
			<div id="grid">
				
				
					
<div id="portletwrapper-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d686561646572" class="portletWrapper kssattr-portlethash-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d686561646572">
<div class="portletStaticText portlet-static-site-header">
<!--googleoff: index-->
<div class="grid_6 alpha" id="banner"><a href="https://ocw.mit.edu/"><img src="../../../common/images/ocw_mast.png" class="logo" alt="MIT OpenCourseWare, Massachusetts Institute of Technology"></a></div>
<div class="grid_6 omega" id="subscribe">
<aside class="module" aria-label="Connect with OCW">
<table class="social">
    <tbody>
        <tr>
            <td class="socialbutton"><a aria-label="Subscribe to the OCW Newsletter" href="https://ocw.mit.edu/subscribe/index.htm?utm_source=header"><img src="../../../common/images/trans.gif" alt="An icon depicting an envelope.">Subscribe to the OCW Newsletter</a></td>
            <td>
<a aria-label="Facebook" href="https://facebook.com/mitocw"><img src="../../../common/images/icon_fb.png" alt="Click to visit our Facebook page."></a>  <a aria-label="Instagram" href="https://www.instagram.com/mitocw/"><img src="https://ocw.mit.edu/images/icon_ig.png" alt="Click to visit our Instagram page."></a> <a aria-label="Twitter" href="https://twitter.com/mitocw"><img src="https://ocw.mit.edu/images/icon_twitter.png" alt="Click to visit our Twitter feed."></a><a aria-label="YouTube" href="https://www.youtube.com/mitocw" style="font-size: 12.208px;"><img src="https://ocw.mit.edu/images/icon_yt.png" alt="Click to visit our YouTube page."></a><span style="font-size: 12.208px;">   </span><a aria-label="Open Matters blog on WordPress" href="https://www.ocw-openmatters.org/" style="font-size: 12.208px;"><img src="https://ocw.mit.edu/images/icon_wp.png" alt="Click to visit our blog on WordPress."></a>
</td>
        </tr>
    </tbody>
</table>
</aside><nav aria-label="Help Links" class="helplinks">     <a aria-label="OCW Site Help" href="https://ocw.mit.edu/help">Help</a><span aria-hidden="true">|</span>     <a href="../../../common/about/contactus.htm">Contact Us</a>   </nav>
</div>
<div class="clear"> </div>
<!--googleon: index-->
</div>

</div>

<div id="portletwrapper-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a6d6567612d6d656e75" class="portletWrapper kssattr-portlethash-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a6d6567612d6d656e75">
<div class="portletStaticText portlet-static-mega-menu"><div><nav id="mega" class="grid_8 alpha" aria-label="Site">
<ul id="menu" role="presentation">
    <li id="menu_home">
<a href="https://ocw.mit.edu/" aria-label="Homepage"><img src="../../../common/images/top-nav_home.png" class="home_icon" alt="Click for site home page."></a><!-- Begin Home Item -->
</li>
    <!-- End Home Item -->
    <li id="drop_1" aria-label="Find Courses">
<a href="#" aria-hidden="true">FIND COURSES</a><!-- Begin 5 columns Item -->
    <div class="dropdown_5columns-a mega-courses">
    <div class="col_1a">
    <div class="row_1a">
<nav aria-labelledby="mm-find-courses-by">     <span id="mm-find-courses-by" class="nav" aria-hidden="true">Find courses by:</span>
    <ul class="find_by" role="presentation">
        <li><a href="https://ocw.mit.edu/courses/find-by-topic/">Topic</a></li>
        <li><a href="https://ocw.mit.edu/courses/find-by-number/">MIT Course Number</a></li>
        <li><a href="https://ocw.mit.edu/courses/find-by-department/">Department</a></li>
    </ul>
    </nav>     <nav aria-labelledby="mm-collections">     <span id="mm-collections" class="nav" aria-hidden="true">Collections</span>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/new-courses/">New Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/most-visited-courses/">Most Visited Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/ocw-scholar/">OCW Scholar Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/audio-video-courses/">Audio/Video Lectures</a></li>
        <li><a href="https://ocw.mit.edu/courses/online-textbooks/">Online Textbooks</a></li>
        <li><a href="https://ocw.mit.edu/resources/">Supplemental Resources</a></li>
        <li><a href="https://ocw.mit.edu/high-school/">OCW Highlights for High School</a></li>
        <li><a href="https://ocw.mit.edu/courses/mitx-related-courseware/">MITx &amp; Related OCW Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/mit-open-learning-library/">MIT Open Learning Library</a></li>
    </ul>
    </nav>     <nav class="col_1b" aria-labelledby="mm-translated-courses">     <span id="mm-translated-courses" class="nav" aria-hidden="true" style="line-height: 1.3;">Cross-Disciplinary Topic Lists</span>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/energy-courses">Energy</a></li>
        <li><a href="https://ocw.mit.edu/courses/entrepreneurship">Entrepreneurship</a></li>
        <li><a href="https://ocw.mit.edu/courses/environment-courses">Environment</a></li>
        <li><a href="https://ocw.mit.edu/courses/intro-programming">Introductory Programming</a></li>
        <li><a href="https://ocw.mit.edu/courses/life-sciences">Life Sciences</a></li>
        <li><a href="https://ocw.mit.edu/courses/transportation-courses">Transportation</a></li>
    </ul>
    </nav>
</div>
    <div class="row_1b"><nav aria-labelledby="mm-cross-disciplinary-topic-lists">     <span id="mm-cross-disciplinary-topic-lists" class="nav" aria-hidden="true">Translated Courses</span>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/translated-courses/traditional-chinese" aria-label="Traditional Chinese">繁體字 / Traditional Chinese</a></li>
        <li><a href="https://ocw.mit.edu/courses/translated-courses/turkish" aria-label="Turkish">Türkçe / Turkish</a></li>
        <li><a href="https://ocw.mit.edu/courses/translated-courses/korean" aria-label="Korean">(비디오)한국 / Korean</a></li>
    </ul>
    </nav></div>
    </div>
    </div>
    </li>
    <li id="drop_2">
<a href="#" aria-label="For Educators">For Educators</a>
    <div class="dropdown_1column-a" style="width: 270px;"><nav aria-labelledby="mm-find-courses-by">
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/educator/chalk-radio-podcast">Chalk Radio Podcast</a></li>
        <li><a href="https://ocw.mit.edu/educator/">OCW Educator Portal</a></li>
    </ul>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/instructor-insights/">Instructor Insights by Department</a></li>
        <li><a href="https://openlearning.mit.edu/campus/digital-innovations/">Residential Digital Innovations </a></li>
    </ul>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/high-school/">OCW Highlights for High School</a></li>
    </ul>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/educator/additional-resources/">Additional Resources</a></li>
    </ul>
    </nav></div>
    </li>
    <li id="drop_3">
<a href="#" aria-hidden="true">Give Now</a>
    <div class="dropdown_1column-a"><nav class="col_1" aria-label="Donate">
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/give/">Make a Donation</a></li>
        <li><a href="https://ocw.mit.edu/give/why-give/">Why Give?</a></li>
        <li><a href="https://ocw.mit.edu/give/our-supporters/">Our Supporters</a></li>
        <li><a href="https://ocw.mit.edu/give/other-ways-to-contribute/">Other Ways to Contribute</a></li>
        <li><a href="https://ocw.mit.edu/support/">Become a Corporate Sponsor</a></li>
    </ul>
    </nav></div>
    </li>
    <li id="drop_4">
<a href="#" aria-hidden="true">About</a>
    <div class="dropdown_1column-a"><nav class="col_1" aria-label="About">
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/about/">About MIT OpenCourseWare</a></li>
        <li><a href="https://ocw.mit.edu/about/site-statistics/">Site Statistics</a></li>
        <li><a href="https://ocw.mit.edu/about/ocw-stories/">OCW Stories</a></li>
        <li><a href="https://ocw.mit.edu/about/newsletter/">Newsletter</a></li>
        <li><a href="https://chalk-radio.simplecast.com/">Chalk Radio Podcast</a></li>
        <li><a href="https://www.ocw-openmatters.org/">Open Matters Blog</a></li>
    </ul>
    </nav></div>
    </li>
</ul>
</nav></div></div>

</div>





<!--googleoff: index-->
<script>
  (function() {
	var cx = '012626166551961672889:owjdpuboktq';
	var gcse = document.createElement('script');
	gcse.type = 'text/javascript';
	gcse.async = true;
	gcse.src = 'https://cse.google.com/cse.js?cx=' + cx;
	var s = document.getElementsByTagName('script')[0];
	s.parentNode.insertBefore(gcse, s);
  })();
  window.onload = function(){
	document.getElementById('gsc-i-id1').placeholder = 'Search';	
  };

$(document).ready(function(){

$('.advanceSearch a').keydown(function(event){showSearchTips($(this),event);})
$('#searchTipsModal').keydown(function(event){showSearchTips($(this),event);})

function showSearchTips(obj,evt) {
// if pressed enter key
	if ( evt.which == 13 || evt.which == 32) {
		showModal();
		ga('send', 'pageview', "AdvanceSearch");
		$(".advanceSearch a").attr('aria-expanded', 'true');
		$('.searchTipsModal').focus();
		evt.preventDefault();
		}
	if ( evt.which == 27 ) {
		hideModal();
		$(".advanceSearch a").attr('aria-expanded', 'false');
		var modal = document.getElementById('searchTipsModal');
		modal.style.display = "none";
		$(".advanceSearch a").focus();
		evt.preventDefault();
		}
}

});
function showModal(){
	var modal = document.getElementById('searchTipsModal');
	modal.style.display = "block";
	ga('send', 'pageview', "AdvanceSearch");
	document.getElementById("searchTipsBtn").setAttribute("aria-expanded", true);
	window.setTimeout(function () {
    document.getElementById('searchTipsModal').focus(); }, 0);
}

function hideModal(){
	var modal = document.getElementById('searchTipsModal');
	modal.style.display = "none";
	document.getElementById("searchTipsBtn").setAttribute("aria-expanded", false);
}
</script>
<div id="search" role="search" class="grid_4 omega">
    	<table class="search">
				<tbody>
					<tr>
						<td><div class="searchboxheader"><searchbox-only resultsurl="/search/ocwsearch.htm"></searchbox-only></div></td>
						<td>
							<div class="advanceSearch">
								<a id="searchTipsBtn" onclick="showModal();" href="#" role="button" aria-label="search tips" aria-expanded="false" aria-describedby="searchtips">Search Tips</a>

								<!-- The Modal -->
								<div id="searchTipsModal" class="modal" tabindex="-1">
								  <!-- Modal content -->
									<div class="modal-content">
										<div class="modal-body">
											<button class="close" onclick="hideModal();" aria-label="close">X</button>
											<span>
												<b>Exclude words from your search</b>
												<br>Put - in front of a word you want to leave out. For example, jaguar speed -car
												<br><br>
												<b>Search for an exact match</b>
												<br>Put a word or phrase inside quotes. For example, "tallest building".
												<br><br>
												<b>Search for wildcards or unknown words</b>
												<br>Put a * in your word or phrase where you want to leave a placeholder. For example, "largest * in the world".
												<br><br>
												<b>Search within a range of numbers</b>
												<br>Put .. between two numbers. For example, camera $50..$100.
												<br><br>
												<b>Combine searches</b>
												<br>Put "OR" between each search query. For example,  marathon OR race.
												<br><br>
											</span>
										</div>
								  </div>
								</div>
							</div>
						</td>
					</tr>
				</tbody>
		</table>
</div>
<div class="clear"></div>
<!--googleon: index-->
<!-- *end header* -->

				
				
			</div>
<!-- top grid end -->
		</header><!-- top end -->
			
		<div id="center_media">
      	<div id="grid">
      		<div id="left">
        		<nav id="breadcrumb_media" aria-label="Breadcrumb">
                	<p>

    <a href="https://ocw.mit.edu/">Home</a>
    
        »
        
    
    
        
            <a href="https://ocw.mit.edu/courses">Courses</a>
            
                »
                
            
            
         
    
    
        
            <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science">Electrical Engineering and Computer Science</a>
            
                »
                
            
            
         
    
    
        
            <a href="../../../contents/index.htm">Mathematics for Computer Science</a>
            
                »
                
            
            
         
    
    
        
            <a href="../../../contents/video-lectures/index.htm">Video Lectures</a>
            
                »
                
            
            
         
    
    
        
            
            
            Lecture 1: Introduction and Proofs
         
    
</p>

            	</nav>
            	<div class="clear"></div>
        		<div id="media_title">
        		<h1 class="title" itemprop="name" property="dct:title">
        <span class="" id="parent-fieldname-title">
            Lecture 1: Introduction and Proofs
        </span>
    </h1>
        		</div>
           		<div class="clear"></div>
           		<div id="course_wrapper_media">
           			<nav id="course_nav" aria-label="Course">
           				<script language="javascript" type="text/javascript">
function toggleMenu(objID) {
  if (!document.getElementById) return;
  var ob = document.getElementById(objID);
  ob.className = (ob.className == 'selected')?'': 'selected';
}
function toggleClass(id)
{
  var divtoggleClass= document.getElementById(id);
  divtoggleClass.className = (divtoggleClass.className == 'mO')?'mC': 'mO';
  return false;
}
function changeAlt(id)
{
  id.alt = (id.alt == 'Expand Menu')?'Collapse Menu' : 'Expand Menu';
  id.title = (id.title == 'Expand Menu')?'Collapse Menu' : 'Expand Menu';
}
</script>
<!--Left Nav Starts -->


	<ul>			  
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/index.htm">
		                  Course Home  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/syllabus/index.htm">
		                  Syllabus  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/calendar/index.htm">
		                  Calendar  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/readings/index.htm">
		                  Readings  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="selected">
			   			<a href="../../../contents/video-lectures/index.htm">
		                  Video Lectures  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/recitations/index.htm">
		                  Recitations  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/assignments/index.htm">
		                  Assignments  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/exams/index.htm">
		                  Exams  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    
		    
         	
	<!--second tal block close-->  
	
</ul>


<!--Left Nav Ends -->





           			</nav>
           			<main id="course_inner_media" aria-labelledby="media_title">
      					 
        <div class="" id="parent-fieldname-text">
            
            
        </div>
    
      					     
    
    



<script type="text/javascript">var caption_embed_1 ={'English - US': '/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-1-introduction-and-proofs/L3LMbpZIKhQ.srt'}</script>     
     <div id="media-embed">
         <div class="attention_message" id="embed_1">
<p>Flash and JavaScript are required for this feature.</p>
<p>Download the video from <a href="http://itunes.apple.com/us/itunes-u/lecture-1-introduction-proofs/id503873536?i=110644965">iTunes U</a> or the <a href="http://www.archive.org/download/MIT6.042JF10/MIT6_042JF10_lec01_300k.mp4">Internet Archive</a>.</p>
</div>
     </div>
    
     <script type="text/javascript">ocw_embed_chapter_media('embed_1', 'https://www.youtube.com/v/L3LMbpZIKhQ', 'youtube', '/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-1-introduction-and-proofs', 'https://img.youtube.com/vi/L3LMbpZIKhQ/0.jpg',0,0, 'https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-1-introduction-and-proofs/L3LMbpZIKhQ.srt')</script>
	 
	 
	 		
	 		<div id="transcript1"></div>
				 <script type="text/javascript">createThreePlayParams(2, 781474, "embed_1", 0, 0)</script>
			 
	

     <div id="media_resource_next_prev_nav" style="margin-top: 1em;">
        <p>
        
     	
        
            <a href="../../../contents/video-lectures/lecture-2-induction/index.htm"> 
                <img src="../../../common/images/btn_next_resource.png" alt="Next track" title="Next track"></a>
       
       </p>
     </div>
 


<script type="text/javascript">
		window.onload=function(){
		init();
		
		}
		var tabLinks = new Array();
		var contentDivs = new Array();
		function init() {
		  // Grab the tab links and content divs from the page
		  var tabListItems = document.getElementById('tabs').childNodes;
		  for ( var i = 0; i < tabListItems.length; i++ ) {
			if ( tabListItems[i].nodeName == "LI" ) {
			  var tabLink = getFirstChildWithTagName( tabListItems[i], 'A' );
			  var id = getHash( tabLink.getAttribute('href') );
			  tabLinks[id] = tabLink;
			  contentDivs[id] = document.getElementById( id );
			}
		  }
		  // Assign onclick events to the tab links, and
		  // highlight the first tab
		  var i = 0;
		  for ( var id in tabLinks ) {
			tabLinks[id].onclick = showTab;
			tabLinks[id].onfocus = function() { this.blur() };
			if ( i == 0 ) tabLinks[id].className = 'selected';
			i++;
		  }
		  // Hide all content divs except the first
		  var i = 0;
		  for ( var id in contentDivs ) {
			if ( i != 0 ) contentDivs[id].className = 'tabContent hide';
			i++;
		  }
		}
		function showTab() {
		  var selectedId = getHash( this.getAttribute('href') );
		  // Highlight the selected tab, and dim all others.
		  // Also show the selected content div, and hide all others.
		  for ( var id in contentDivs ) {
			if ( id == selectedId ) {
			  tabLinks[id].className = 'selected';
			  contentDivs[id].className = 'tabContent';
			} else {
			  tabLinks[id].className = '';
			  contentDivs[id].className = 'tabContent hide';
			}
		  }
		  // Stop the browser following the link
		  return false;
		}
		function getFirstChildWithTagName( element, tagName ) {
		  for ( var i = 0; i < element.childNodes.length; i++ ) {
			if ( element.childNodes[i].nodeName == tagName ) return element.childNodes[i];
		  }
		}
		function getHash( url ) {
		  var hashPos = url.lastIndexOf ( '#' );
		  return url.substring( hashPos + 1 );
		}
 </script>	
 

  <div id="media_tabs">
     
        <ul id="tabs">
            <li class="first">
                <a href="#vid_about" class="selected">About this Video</a>
            </li>
            <li class="">
                <a href="#vid_index" class="">Playlist</a>
            </li>
            <li class="">
                <a href="#vid_playlist" class="">Transcript</a>
            </li>
            <li class="">
                <a href="#vid_related" class="">Download this Video</a>
            </li>
        </ul>
   
        <div id="vid_about" itemprop="description" class="tabContent">
<p><strong>Description:</strong> Introduction to mathematical proofs using axioms and propositions. Covers basics of truth tables and implications, as well as some famous hypotheses and conjectures.</p> <p><strong>Speaker:</strong> Tom Leighton</p>
</div>
        <div id="vid_index" itemprop="description" class="tabContent hide">
<div class="related-media-thumbnail-nolink">
<div class="now-playing-resource">Now Playing</div>
<img src="https://img.youtube.com/vi/L3LMbpZIKhQ/default.jpg" title="Lecture 1: Introduction and Proofs" alt="Lecture 1: Introduction and Proofs">
<p>Lecture 1: Introduction and...</p>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-2-induction/index.htm">
<img src="https://img.youtube.com/vi/z8HKWUWS-lA/default.jpg" title="Lecture 2: Induction" alt="Lecture 2: Induction">
<p>Lecture 2: Induction</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-3-strong-induction/index.htm">
<img src="https://img.youtube.com/vi/NuGDkmwEObM/default.jpg" title="Lecture 3: Strong Induction" alt="Lecture 3: Strong Induction">
<p>Lecture 3: Strong Induction</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-4-number-theory-i/index.htm">
<img src="https://img.youtube.com/vi/NuY7szYSXSw/default.jpg" title="Lecture 4: Number Theory I" alt="Lecture 4: Number Theory I">
<p>Lecture 4: Number Theory I</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-5-number-theory-ii/index.htm">
<img src="https://img.youtube.com/vi/XX7ePR21Ook/default.jpg" title="Lecture 5: Number Theory II" alt="Lecture 5: Number Theory II">
<p>Lecture 5: Number Theory II</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-6-graph-theory-and-coloring/index.htm">
<img src="https://img.youtube.com/vi/h9wxtqoa1jY/default.jpg" title="Lecture 6: Graph Theory and Coloring" alt="Lecture 6: Graph Theory and Coloring">
<p>Lecture 6: Graph Theory and...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-7-matching-problems/index.htm">
<img src="https://img.youtube.com/vi/5RSMLgy06Ew/default.jpg" title="Lecture 7: Matching Problems" alt="Lecture 7: Matching Problems">
<p>Lecture 7: Matching Problems</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-8-graph-theory-ii-minimum-spanning-trees/index.htm">
<img src="https://img.youtube.com/vi/GJpt_3ie4WU/default.jpg" title="Lecture 8: Graph Theory II: Minimum Spanning Trees" alt="Lecture 8: Graph Theory II: Minimum Spanning Trees">
<p>Lecture 8: Graph Theory II:...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-9-communication-networks/index.htm">
<img src="https://img.youtube.com/vi/bTyxpoi2dmM/default.jpg" title="Lecture 9: Communication Networks" alt="Lecture 9: Communication Networks">
<p>Lecture 9: Communication Ne...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-10-graph-theory-iii/index.htm">
<img src="https://img.youtube.com/vi/DOIp5D7VMS4/default.jpg" title="Lecture 10: Graph Theory III" alt="Lecture 10: Graph Theory III">
<p>Lecture 10: Graph Theory III</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-11-relations-partial-orders-and-scheduling/index.htm">
<img src="https://img.youtube.com/vi/1nScXLQAQ9A/default.jpg" title="Lecture 11: Relations, Partial Orders, and Scheduling" alt="Lecture 11: Relations, Partial Orders, and Scheduling">
<p>Lecture 11: Relations, Part...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-12-sums/index.htm">
<img src="https://img.youtube.com/vi/fAeShezAGLE/default.jpg" title="Lecture 12: Sums" alt="Lecture 12: Sums">
<p>Lecture 12: Sums</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-13-sums-and-asymptotics/index.htm">
<img src="https://img.youtube.com/vi/X9eErxRjQEI/default.jpg" title="Lecture 13: Sums and Asymptotics" alt="Lecture 13: Sums and Asymptotics">
<p>Lecture 13: Sums and Asympt...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-14-divide-and-conquer-recurrences/index.htm">
<img src="https://img.youtube.com/vi/Kqf0uO0oV6s/default.jpg" title="Lecture 14: Divide and Conquer Recurrences" alt="Lecture 14: Divide and Conquer Recurrences">
<p>Lecture 14: Divide and Conq...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-15-linear-recurrences/index.htm">
<img src="https://img.youtube.com/vi/TWBB-JlmYUc/default.jpg" title="Lecture 15: Linear Recurrences" alt="Lecture 15: Linear Recurrences">
<p>Lecture 15: Linear Recurrences</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-16-counting-rules-i/index.htm">
<img src="https://img.youtube.com/vi/pNt5Ll6hGqo/default.jpg" title="Lecture 16: Counting Rules I" alt="Lecture 16: Counting Rules I">
<p>Lecture 16: Counting Rules I</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-17-counting-rules-ii/index.htm">
<img src="https://img.youtube.com/vi/09yIb3VHhMI/default.jpg" title="Lecture 17: Counting Rules II" alt="Lecture 17: Counting Rules II">
<p>Lecture 17: Counting Rules II</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-18-probability-introduction/index.htm">
<img src="https://img.youtube.com/vi/SmFwFdESMHI/default.jpg" title="Lecture 18: Probability Introduction" alt="Lecture 18: Probability Introduction">
<p>Lecture 18: Probability Int...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-19-conditional-probability/index.htm">
<img src="https://img.youtube.com/vi/E6FbvM-FGZ8/default.jpg" title="Lecture 19: Conditional Probability" alt="Lecture 19: Conditional Probability">
<p>Lecture 19: Conditional Pro...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-20-independence/index.htm">
<img src="https://img.youtube.com/vi/l1BCv3qqW4A/default.jpg" title="Lecture 20: Independence" alt="Lecture 20: Independence">
<p>Lecture 20: Independence</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-21-random-variables/index.htm">
<img src="https://img.youtube.com/vi/MOfhhFaQdjw/default.jpg" title="Lecture 21: Random Variables" alt="Lecture 21: Random Variables">
<p>Lecture 21: Random Variables</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-22-expectation-i/index.htm">
<img src="https://img.youtube.com/vi/gGlMSe7uEkA/default.jpg" title="Lecture 22: Expectation I" alt="Lecture 22: Expectation I">
<p>Lecture 22: Expectation I</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-23-expectation-ii/index.htm">
<img src="https://img.youtube.com/vi/oI9fMUqgfxY/default.jpg" title="Lecture 23: Expectation II" alt="Lecture 23: Expectation II">
<p>Lecture 23: Expectation II</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-24-large-deviations/index.htm">
<img src="https://img.youtube.com/vi/q4mwO2qS2z4/default.jpg" title="Lecture 24: Large Deviations" alt="Lecture 24: Large Deviations">
<p>Lecture 24: Large Deviations</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-25-random-walks/index.htm">
<img src="https://img.youtube.com/vi/56iFMY8QW2k/default.jpg" title="Lecture 25: Random Walks" alt="Lecture 25: Random Walks">
<p>Lecture 25: Random Walks</p></a>
</div>
</div>
        <div id="vid_playlist" itemprop="description" class="tabContent hide">
<ul><li><a class="transcript-link" title="Open in a new window." alt="Open in a new window." style="text-decoration: none; font-size: 1.0em;" target="_blank" text-decoration: none font-size: href="../../../contents/video-lectures/lecture-1-introduction-and-proofs/L3LMbpZIKhQ.pdf"> Download English-US transcript (PDF)</a></li></ul>
<p><span m="570">The</span> <span m="680">following</span> <span m="1120">content</span> <span m="1710">is</span> <span m="1830">provided</span> <span m="2270">under</span> <span m="2550">a</span> <span m="2590">Creative</span> <span m="2990">Commons</span> <span m="3400">license.</span> <span m="4510">Your</span> <span m="4700">support</span> <span m="5200">will</span> <span m="5360">help</span> <span m="5600">MIT</span> <span m="6060">OpenCourseWare</span> <span m="6850">continue</span> <span m="7360">to</span> <span m="7440">offer</span> <span m="7850">high</span> <span m="8090">quality</span> <span m="8610">educational</span> <span m="9240">resources</span> <span m="9860">for</span> <span m="10010">free.</span> <span m="11220">To</span> <span m="11320">make</span> <span m="11430">a</span> <span m="11470">donation</span> <span m="12160">or</span> <span m="12430">view</span> <span m="12870">additional</span> <span m="13290">materials</span> <span m="13830">from</span> <span m="13980">hundreds</span> <span m="14410">of</span> <span m="14520">MIT</span> <span m="14950">courses,</span> <span m="16050">visit</span> <span m="16280">MIT</span> <span m="16700">OpenCourseWare</span> <span m="17740">at</span> <span m="17910">ocw.mit.edu.</span> </p>
<p><span m="24070">PROFESSOR: Who</span> <span m="24280">can</span> <span m="24420">tell</span> <span m="24540">me</span> <span m="24640">what</span> <span m="24770">a</span> <span m="24830">proof</span> <span m="25100">is?</span> <span m="26540">Any</span> <span m="26720">ideas</span> <span m="27180">of,</span> <span m="27760">what</span> <span m="28210">is</span> <span m="28490">a</span> <span m="28570">proof,</span> <span m="28950">anyway?</span> <span m="29570">Any</span> <span m="29740">thoughts?</span> <span m="30000">Yeah?</span> </p>
<p><span m="30874">AUDIENCE: It's</span> <span m="31358">a</span> <span m="31842">chain of</span> <span m="32326">statements,</span> <span m="33294">each</span> <span m="33778">logically</span> <span m="34262">supported by</span> <span m="34746">the</span> <span m="35230">previous</span> <span m="35660">ones,</span> <span m="36030">that get</span> <span m="36400">you</span> <span m="36770">from</span> <span m="37150">a</span> <span m="38044">set</span> <span m="38491">of</span> <span m="38938">assumptions to</span> <span m="39385">a set of</span> <span m="39832">conclusions.</span> </p>
<p><span m="40730">PROFESSOR: Very</span> <span m="41390">good.</span> <span m="41810">I</span> <span m="41940">like</span> <span m="42160">that.</span> <span m="42640">That's</span> <span m="43350">very</span> <span m="43650">close</span> <span m="43980">to</span> <span m="44100">what</span> <span m="44270">we're</span> <span m="44400">going</span> <span m="44510">to</span> <span m="44580">do</span> <span m="44780">here,</span> <span m="45460">yeah.</span> <span m="47090">Now,</span> <span m="47210">that's</span> <span m="47450">a</span> <span m="47820">special</span> <span m="48150">kind</span> <span m="48370">of</span> <span m="48460">proof,</span> <span m="48760">though.</span> <span m="50110">That's</span> <span m="50340">a</span> <span m="50410">mathematical</span> <span m="51120">proof.</span> <span m="52290">And</span> <span m="52720">I'm</span> <span m="52860">going</span> <span m="52940">to</span> <span m="53010">write</span> <span m="53190">a</span> <span m="53290">definition</span> <span m="53920">very</span> <span m="54170">close</span> <span m="54460">to</span> <span m="54540">that</span> <span m="54760">in</span> <span m="54830">a</span> <span m="54880">few</span> <span m="55050">minutes.</span> </p>
<p><span m="56610">But</span> <span m="57310">proofs</span> <span m="57720">exist</span> <span m="58110">beyond</span> <span m="58640">mathematics.</span> <span m="60830">Can</span> <span m="60960">anybody</span> <span m="62030">think</span> <span m="62270">of</span> <span m="62350">a</span> <span m="62400">higher</span> <span m="62910">level</span> <span m="63960">notion</span> <span m="64330">of</span> <span m="64400">what</span> <span m="64510">a</span> <span m="64560">proof</span> <span m="64870">is?</span> <span m="65470">That's</span> <span m="65710">correct,</span> <span m="66030">what</span> <span m="66160">you</span> <span m="66250">said,</span> <span m="66540">but</span> <span m="66650">there's</span> <span m="66810">a</span> <span m="66860">higher</span> <span m="67240">meta</span> <span m="67540">level</span> <span m="67870">notion</span> <span m="68200">of</span> <span m="68260">what</span> <span m="68370">a</span> <span m="68430">proof</span> <span m="68700">is</span> <span m="70520">beyond</span> <span m="70920">that.</span> <span m="72500">It may</span> <span m="72650">have</span> <span m="72900">no</span> <span m="73120">logical</span> <span m="73560">deductions</span> <span m="74520">potentially.</span> <span m="76220">It may</span> <span m="76400">have</span> <span m="76590">no</span> <span m="76910">assumptions.</span> <span m="78490">Any</span> <span m="78700">thoughts</span> <span m="80350">about a</span> <span m="80460">proof?</span> </p>
<p><span m="82710">OK,</span> <span m="83080">well,</span> <span m="83980">I</span> <span m="84080">think</span> <span m="84480">generally,</span> <span m="86030">a</span> <span m="86500">proof</span> <span m="86970">is</span> <span m="87140">considered,</span> <span m="88300">across</span> <span m="88730">multiple</span> <span m="89080">fields,</span> <span m="89400">as</span> <span m="89510">a</span> <span m="89570">method</span> <span m="90040">for</span> <span m="90190">ascertaining</span> <span m="90790">the</span> <span m="90880">truth.</span> <span m="96720">And</span> <span m="96960">you</span> <span m="97110">described</span> <span m="97680">one</span> <span m="97860">method.</span> <span m="111370">Now,</span> <span m="111570">by</span> <span m="111730">ascertaining,</span> <span m="112400">I</span> <span m="112450">mean</span> <span m="112840">establishing</span> <span m="113600">truth,</span> <span m="113980">verifying</span> <span m="114720">truth.</span> <span m="116340">And</span> <span m="116490">there's</span> <span m="116660">lots</span> <span m="116980">of</span> <span m="117070">ways</span> <span m="117620">to</span> <span m="117870">ascertain</span> <span m="118430">truth</span> <span m="118930">in</span> <span m="119220">society,</span> <span m="119910">and</span> <span m="120100">even</span> <span m="120330">within</span> <span m="120600">science.</span> <span m="122540">What</span> <span m="122680">are</span> <span m="122750">some</span> <span m="122890">examples</span> <span m="123980">of</span> <span m="124360">ways</span> <span m="124820">that</span> <span m="124910">we</span> <span m="125050">ascertain</span> <span m="125660">truth</span> <span m="126910">in</span> <span m="127100">society?</span> <span m="130210">Yeah?</span> </p>
<p><span m="130897">AUDIENCE: Observations,</span> <span m="132120">like</span> <span m="132690">seeing</span> <span m="133060">that</span> <span m="133320">piece</span> <span m="133469">of</span> <span m="133618">chalk</span> <span m="133768">will fall</span> <span m="134216">to the</span> <span m="134664">ground.</span> </p>
<p><span m="135560">PROFESSOR: Observation,</span> <span m="136950">experiment</span> <span m="137260">and</span> <span m="137570">observation--</span> <span m="138190">excellent.</span> <span m="138640">And that's</span> <span m="139380">the</span> <span m="139880">bedrock</span> <span m="140860">of</span> <span m="140970">physics.</span> <span m="143540">I</span> <span m="143600">mean,</span> <span m="143820">who</span> <span m="143920">really</span> <span m="144210">knows</span> <span m="144470">if</span> <span m="144560">there's</span> <span m="144750">gravity</span> <span m="145210">out</span> <span m="145350">there?</span> <span m="147580">Well,</span> <span m="147820">we</span> <span m="147950">observe</span> <span m="148450">it.</span> <span m="149720">And</span> <span m="149880">so</span> <span m="150070">we</span> <span m="150380">then</span> <span m="150810">conclude</span> <span m="151140">that's</span> <span m="151360">the</span> <span m="151440">truth.</span> <span m="151730">There's</span> <span m="151940">gravity,</span> <span m="152450">and</span> <span m="152530">we</span> <span m="152600">have</span> <span m="152740">laws</span> <span m="153020">about</span> <span m="153420">it.</span> </p>
<p><span m="153660">That's</span> <span m="153870">one</span> <span m="154080">good</span> <span m="154220">way.</span> <span m="154440">What's</span> <span m="154650">another</span> <span m="154930">way</span> <span m="155260">of</span> <span m="155730">ascertaining</span> <span m="156320">truth</span> <span m="159890">across</span> <span m="160260">scientific</span> <span m="160890">disciplines,</span> <span m="161320">or</span> <span m="162840">beyond</span> <span m="163200">science,</span> <span m="163630">just</span> <span m="163830">in</span> <span m="163880">society?</span> <span m="165150">How</span> <span m="165240">is</span> <span m="165360">truth</span> <span m="165650">established?</span> <span m="167990">What</span> <span m="168090">are</span> <span m="168130">the</span> <span m="168210">ways?</span> <span m="168450">Yeah?</span> </p>
<p><span m="168760">AUDIENCE: Well,</span> <span m="169246">establishing</span> <span m="169732">what's</span> <span m="170218">false,</span> <span m="170704">you</span> <span m="171190">can</span> <span m="171676">know</span> <span m="172162">what</span> <span m="172648">things aren't</span> <span m="173134">true.</span> <span m="173620">Then that</span> <span m="174106">helps you</span> <span m="175080">narrow down</span> <span m="175580">what is</span> <span m="175940">true.</span> </p>
<p><span m="176460">PROFESSOR: Yes,</span> <span m="176840">truth--</span> <span m="177350">yeah,</span> <span m="177500">that's</span> <span m="177680">great.</span> <span m="177900">Truth</span> <span m="178060">is</span> <span m="178180">the</span> <span m="178310">opposite</span> <span m="178730">of</span> <span m="178810">falsehood.</span> <span m="179980">How</span> <span m="180120">do</span> <span m="180190">we</span> <span m="180310">establish</span> <span m="180740">falsehood?</span> <span m="182590">What</span> <span m="182740">are</span> <span m="182770">the</span> <span m="182890">ways</span> <span m="183190">in</span> <span m="183450">doing that?</span> <span m="184460">How</span> <span m="184590">you</span> <span m="184690">decide</span> <span m="185010">something</span> <span m="185270">is</span> <span m="185370">not</span> <span m="185620">true</span> <span m="187120">in</span> <span m="187250">every</span> <span m="187400">day--</span> <span m="187630">yeah?</span> </p>
<p><span m="188455">AUDIENCE: Find</span> <span m="188870">counterexamples.</span> </p>
<p><span m="190100">PROFESSOR: Find</span> <span m="190430">counterexamples,</span> <span m="191850">yeah,</span> <span m="192330">that's</span> <span m="192640">good.</span> <span m="193460">So</span> <span m="194150">in</span> <span m="194900">fact,</span> <span m="195110">even</span> <span m="195260">a</span> <span m="195320">step</span> <span m="195540">more</span> <span m="195800">general,</span> <span m="196580">sampling.</span> <span m="200030">Counterexamples</span> <span m="201200">are</span> <span m="201290">ways.</span> <span m="206320">If</span> <span m="206380">you</span> <span m="206470">do</span> <span m="206660">something,</span> <span m="207110">an</span> <span m="207210">experiment,</span> <span m="207660">ten</span> <span m="207880">times,</span> <span m="208400">and</span> <span m="208830">every</span> <span m="209070">time,</span> <span m="209310">it</span> <span m="209360">comes</span> <span m="209580">out</span> <span m="209690">one</span> <span m="209850">way,</span> <span m="211050">that's</span> <span m="211280">truth,</span> <span m="212140">maybe.</span> <span m="213310">But</span> <span m="213440">there's</span> <span m="213620">fields</span> <span m="213920">where</span> <span m="213970">that</span> <span m="214130">becomes</span> <span m="214420">truth.</span> <span m="216460">What</span> <span m="216590">about</span> <span m="216750">other</span> <span m="216940">ways?</span> </p>
<p><span m="221490">How</span> <span m="221700">are</span> <span m="221790">we</span> <span m="221910">going</span> <span m="222000">to</span> <span m="222060">decide</span> <span m="223140">if</span> <span m="223530">Roger</span> <span m="224010">Clemens</span> <span m="224600">is</span> <span m="224760">guilty</span> <span m="225080">of</span> <span m="225150">perjury</span> <span m="226860">for</span> <span m="226980">lying</span> <span m="227340">about</span> <span m="227570">steroids</span> <span m="228050">to</span> <span m="228140">Congress?</span> <span m="231210">He</span> <span m="231410">did it</span> <span m="231760">or he</span> <span m="231970">didn't.</span> <span m="232230">How</span> <span m="232420">are we</span> <span m="232550">going</span> <span m="232630">to</span> <span m="232680">decide</span> <span m="233120">that?</span> <span m="234300">How is</span> <span m="234580">that</span> <span m="234690">truth</span> <span m="234800">going</span> <span m="234910">to</span> <span m="234950">be</span> <span m="235080">ascertained?</span> <span m="236290">Yeah?</span> </p>
<p><span m="236550">AUDIENCE:  Would</span> <span m="237001">it be</span> <span m="237452">by</span> <span m="237903">examining</span> <span m="238805">the</span> <span m="239256">evidence that</span> <span m="239707">we have?</span> </p>
<p><span m="240610">PROFESSOR: Examining</span> <span m="241000">evidence.</span> <span m="241350">And</span> <span m="241460">who</span> <span m="241670">makes</span> <span m="241950">the</span> <span m="242100">conclusion</span> <span m="242395">there?</span> </p>
<p><span m="243836">AUDIENCE: Juries.</span> </p>
<p><span m="244220">PROFESSOR: The</span> <span m="244320">jury.</span> <span m="245540">Truth</span> <span m="245920">is</span> <span m="246050">established</span> <span m="246560">by</span> <span m="246720">juries</span> <span m="247250">or</span> <span m="247340">judges.</span> <span m="253960">You</span> <span m="254050">know,</span> <span m="254770">Blago--</span> <span m="255240">I can</span> <span m="255510">never pronounce</span> <span m="255859">his name,</span> <span m="256209">the</span> <span m="256600">Illinois</span> <span m="257010">governor,</span> <span m="257430">Blagojevick--</span> <span m="259019">he's</span> <span m="259300">guilty.</span> <span m="260950">That's</span> <span m="261209">the</span> <span m="261290">truth</span> <span m="264175">of--</span> <span m="264590">not</span> <span m="264780">of</span> <span m="264830">conspiracy,</span> <span m="265880">trying</span> <span m="266130">to</span> <span m="266200">sell</span> <span m="266420">Obama</span> <span m="266480">a</span> <span m="266720">senate</span> <span m="267110">seat,</span> <span m="267910">but</span> <span m="268080">of</span> <span m="268160">lying</span> <span m="268480">to</span> <span m="268540">the</span> <span m="268640">authorities</span> <span m="269050">about</span> <span m="269180">campaign</span> <span m="269610">financing.</span> </p>
<p><span m="270970">OJ</span> <span m="272010">is</span> <span m="272190">guilty--</span> <span m="273280">not</span> <span m="273640">of</span> <span m="273790">killing</span> <span m="274090">his</span> <span m="274220">wife,</span> <span m="275640">but</span> <span m="276440">of</span> <span m="276530">breaking</span> <span m="276940">into</span> <span m="277420">an</span> <span m="277510">apartment</span> <span m="277970">to</span> <span m="278060">steal</span> <span m="278380">back</span> <span m="278650">some</span> <span m="278770">of</span> <span m="278840">his</span> <span m="278990">merchandise.</span> <span m="280850">So</span> <span m="281110">judges</span> <span m="281460">and</span> <span m="281570">juries</span> <span m="282000">make</span> <span m="282170">decisions</span> <span m="282630">on</span> <span m="282770">truth.</span> <span m="283840">What</span> <span m="283980">are</span> <span m="284080">other</span> <span m="284380">truths--</span> <span m="284810">bigger</span> <span m="285160">truths,</span> <span m="285670">even,</span> <span m="285800">than</span> <span m="285900">judges</span> <span m="286250">and</span> <span m="286360">juries,</span> <span m="287620">in</span> <span m="287740">society?</span> <span m="291530">There's</span> <span m="291720">one</span> <span m="292020">really</span> <span m="292330">big</span> <span m="292580">one</span> <span m="292740">that</span> <span m="293130">causes</span> <span m="293470">a</span> <span m="293530">lot</span> <span m="293750">of</span> <span m="294380">issues.</span> <span m="294760">Yeah?</span> </p>
<p><span m="295180">AUDIENCE: Religion.</span> </p>
<p><span m="295870">PROFESSOR: What is</span> <span m="296000">it?</span> </p>
<p><span m="296420">AUDIENCE: Religion.</span> </p>
<p><span m="296840">PROFESSOR: Religion,</span> <span m="297300">the</span> <span m="297390">word</span> <span m="297640">of</span> <span m="297770">God--</span> <span m="299800">broadly</span> <span m="300220">construed</span> <span m="300700">here,</span> <span m="301940">for</span> <span m="302090">religion.</span> <span m="305440">Now,</span> <span m="305750">that one</span> <span m="305890">is really</span> <span m="306150">hard</span> <span m="306400">to</span> <span m="306480">argue</span> <span m="306830">about</span> <span m="308140">because</span> <span m="308570">you</span> <span m="308700">believe</span> <span m="309150">it.</span> <span m="310750">And</span> <span m="311250">especially</span> <span m="311620">if</span> <span m="311690">you're</span> <span m="311790">not</span> <span m="312260">talking</span> <span m="312560">to</span> <span m="312620">God</span> <span m="312900">regularly</span> <span m="313440">and</span> <span m="313690">somebody</span> <span m="314030">is,</span> <span m="314310">well,</span> <span m="314590">it's</span> <span m="315010">hard</span> <span m="315250">to</span> <span m="315330">argue</span> <span m="315860">about</span> <span m="316730">the</span> <span m="316880">truth.</span> <span m="318060">So</span> <span m="318180">you</span> <span m="318300">rely</span> <span m="318570">on</span> <span m="318650">others</span> <span m="318890">to</span> <span m="318990">interpret it</span> <span m="319490">for</span> <span m="319700">you,</span> <span m="319820">often--</span> <span m="320475">a</span> <span m="320730">priest,</span> <span m="321310">or a</span> <span m="321420">minister,</span> <span m="321890">a rabbi.</span> <span m="323560">And</span> <span m="323760">it</span> <span m="323830">gets</span> <span m="324200">complicated,</span> <span m="324910">because</span> <span m="324960">you</span> <span m="325070">can</span> <span m="325330">end</span> <span m="325510">up</span> <span m="325640">with</span> <span m="325780">conflicting</span> <span m="326260">truths</span> <span m="327760">based</span> <span m="328020">on</span> <span m="328500">who</span> <span m="328660">you</span> <span m="328740">think</span> <span m="329210">you're</span> <span m="329370">talking</span> <span m="329700">to</span> <span m="329890">or</span> <span m="329980">who</span> <span m="330660">the translator</span> <span m="331190">is</span> <span m="331320">for</span> <span m="331500">you.</span> </p>
<p><span m="333220">Another</span> <span m="333500">one</span> <span m="333650">is</span> <span m="333740">the</span> <span m="333830">word</span> <span m="334070">of</span> <span m="334160">your</span> <span m="334270">boss.</span> <span m="337080">Whatever</span> <span m="337330">the</span> <span m="337420">boss</span> <span m="337750">says</span> <span m="337990">is</span> <span m="338120">right.</span> <span m="339850">Often</span> <span m="340230">in</span> <span m="340300">business,</span> <span m="340820">the</span> <span m="340930">customer</span> <span m="341245">is</span> <span m="341560">always</span> <span m="341860">right.</span> <span m="342650">That's</span> <span m="342890">the</span> <span m="342980">truth,</span> <span m="343170">whatever</span> <span m="343340">the</span> <span m="343540">customer</span> <span m="343940">says.</span> <span m="346680">With</span> <span m="347010">Donald</span> <span m="347390">Trump</span> <span m="347650">as</span> <span m="347740">your</span> <span m="347870">boss,</span> <span m="348320">you'd</span> <span m="348430">better</span> <span m="348670">agree</span> <span m="348920">or</span> <span m="349000">you're</span> <span m="349120">fired.</span> </p>
<p><span m="353560">Often</span> <span m="353950">in</span> <span m="354010">classes,</span> <span m="354520">the</span> <span m="354620">professor</span> <span m="355200">says</span> <span m="355500">it,</span> <span m="355930">it</span> <span m="356060">is</span> <span m="356180">true.</span> <span m="357110">Because</span> <span m="357460">the</span> <span m="357580">authority</span> <span m="358560">said it.</span> <span m="358910">That's</span> <span m="359080">not</span> <span m="359260">true</span> <span m="359460">here.</span> <span m="360290">That</span> <span m="360500">will</span> <span m="360610">not</span> <span m="360800">hold.</span> </p>
<p><span m="361600">And</span> <span m="361770">one</span> <span m="361890">of</span> <span m="361930">the</span> <span m="362020">nicest</span> <span m="362520">things</span> <span m="362650">about</span> <span m="363090">math</span> <span m="363430">that</span> <span m="363540">I</span> <span m="363610">like</span> <span m="363830">a</span> <span m="363890">lot</span> <span m="365340">is</span> <span m="365670">that</span> <span m="365780">the</span> <span m="365900">youngest</span> <span m="366320">student</span> <span m="368490">can</span> <span m="368770">stand</span> <span m="369120">up</span> <span m="369230">against</span> <span m="369650">the</span> <span m="369720">most</span> <span m="370150">oldest,</span> <span m="370620">most</span> <span m="370680">experienced</span> <span m="371070">professor,</span> <span m="372020">and</span> <span m="372260">win</span> <span m="372690">an</span> <span m="372850">argument</span> <span m="374480">on</span> <span m="374670">mathematics.</span> <span m="377520">I</span> <span m="377600">do</span> <span m="377760">get</span> <span m="377940">pleasure</span> <span m="378350">when</span> <span m="378460">a</span> <span m="378500">student</span> <span m="378810">comes</span> <span m="379040">up</span> <span m="379150">and</span> <span m="379250">proves</span> <span m="379490">me</span> <span m="379600">wrong.</span> <span m="379850">I</span> <span m="379970">loved</span> <span m="380360">it</span> <span m="380460">when</span> <span m="380560">that</span> <span m="380710">student</span> <span m="380990">came</span> <span m="381210">in,</span> <span m="381320">and</span> <span m="381400">she</span> <span m="381550">showed</span> <span m="381830">me</span> <span m="382330">what</span> <span m="382530">I</span> <span m="382610">said</span> <span m="382820">really</span> <span m="383240">wasn't</span> <span m="383590">right</span> <span m="383920">when</span> <span m="384020">you</span> <span m="384120">looked</span> <span m="384360">at</span> <span m="384460">it</span> <span m="384540">carefully</span> <span m="385090">or in</span> <span m="385150">a</span> <span m="385230">different</span> <span m="385600">light.</span> </p>
<p><span m="387400">Now,</span> <span m="387990">sometimes</span> <span m="388550">if</span> <span m="388640">I</span> <span m="388710">do</span> <span m="388940">it</span> <span m="388980">on</span> <span m="389070">the</span> <span m="389140">board</span> <span m="389450">here</span> <span m="389680">and</span> <span m="389750">it's</span> <span m="389860">in</span> <span m="389940">class,</span> <span m="390230">well,</span> <span m="391130">that's</span> <span m="391340">fun.</span> <span m="391990">I</span> <span m="392090">feel</span> <span m="392470">a</span> <span m="392510">little</span> <span m="392690">embarrassed</span> <span m="393100">afterwards.</span> <span m="394740">But</span> <span m="394840">it's</span> <span m="394950">a</span> <span m="395020">good</span> <span m="395200">thing</span> <span m="395330">about</span> <span m="395520">mathematics,</span> <span m="396640">is</span> <span m="396840">you</span> <span m="397040">can</span> <span m="397350">have</span> <span m="398560">that</span> <span m="398740">kind</span> <span m="398900">of</span> <span m="398990">dialogue.</span> </p>
<p><span m="401550">OK,</span> <span m="402600">another</span> <span m="403050">one,</span> <span m="403860">which</span> <span m="404060">is</span> <span m="404150">related</span> <span m="404540">to</span> <span m="404620">the</span> <span m="404690">word</span> <span m="404850">of</span> <span m="404940">God</span> <span m="405200">sometimes,</span> <span m="406250">is</span> <span m="406440">inner</span> <span m="406650">conviction--</span> <span m="409650">very</span> <span m="409960">popular</span> <span m="410370">in</span> <span m="410440">computer</span> <span m="410800">science,</span> <span m="411200">believe</span> <span m="411410">it</span> <span m="411460">or</span> <span m="411510">not,</span> <span m="412930">with</span> <span m="413090">the</span> <span m="413420">mantra,</span> <span m="414020">there</span> <span m="414270">are</span> <span m="414390">no</span> <span m="414720">bugs</span> <span m="415130">in</span> <span m="415360">my</span> <span m="415880">program.</span> <span m="417820">I can't</span> <span m="418040">tell</span> <span m="418140">you</span> <span m="418230">how</span> <span m="418400">many</span> <span m="418570">times</span> <span m="418940">you</span> <span m="419570">hear</span> <span m="419700">that.</span> </p>
<p><span m="420850">Closely</span> <span m="421270">related</span> <span m="421940">is,</span> <span m="423050">I</span> <span m="423170">don't</span> <span m="423550">see</span> <span m="423820">why</span> <span m="424080">not</span> <span m="425370">something</span> <span m="425750">is</span> <span m="425840">true.</span> <span m="426790">And</span> <span m="426920">that's</span> <span m="427130">a</span> <span m="427190">good</span> <span m="427420">one,</span> <span m="428070">because</span> <span m="428370">that</span> <span m="428940">transfers</span> <span m="429690">the</span> <span m="429790">burden</span> <span m="430750">of</span> <span m="430910">proof</span> <span m="431400">to</span> <span m="431520">anybody</span> <span m="431930">who</span> <span m="431990">disagrees</span> <span m="432480">with</span> <span m="432610">you.</span> <span m="433906">You</span> <span m="434340">don't</span> <span m="434500">have</span> <span m="434570">to</span> <span m="434670">prove.</span> <span m="434910">You</span> <span m="434970">just say,</span> <span m="435120">I</span> <span m="435220">don't</span> <span m="435370">see</span> <span m="435460">why</span> <span m="435650">it's</span> <span m="435770">not</span> <span m="435940">true.</span> <span m="436550">All of</span> <span m="436760">a sudden,</span> <span m="437100">the</span> <span m="437240">other</span> <span m="437390">person</span> <span m="437690">who's</span> <span m="437800">questioning</span> <span m="438055">you,</span> <span m="438310">it</span> <span m="438380">becomes</span> <span m="438720">their</span> <span m="438970">job</span> <span m="439960">to</span> <span m="440130">disprove</span> <span m="440600">you,</span> <span m="440730">which</span> <span m="440920">is</span> <span m="441060">not</span> <span m="441690">so</span> <span m="441890">good.</span> </p>
<p><span m="444000">OK,</span> <span m="444270">now</span> <span m="444440">in</span> <span m="444530">mathematics,</span> <span m="445440">there's</span> <span m="445660">this</span> <span m="445800">higher</span> <span m="446090">level.</span> <span m="446710">And</span> <span m="446830">someone</span> <span m="447700">stated it</span> <span m="448110">very</span> <span m="448430">clearly</span> <span m="448750">up</span> <span m="448860">there.</span> <span m="448980">Let</span> <span m="449080">me</span> <span m="449170">write</span> <span m="449370">it</span> <span m="449450">up</span> <span m="450310">here.</span> <span m="451460">In</span> <span m="451730">mathematics,</span> <span m="452400">we</span> <span m="452500">have</span> <span m="452660">a</span> <span m="452710">mathematical</span> <span m="455590">proof</span> <span m="459280">is</span> <span m="459560">a</span> <span m="460000">verification</span> <span m="464970">of</span> <span m="465090">a</span> <span m="465170">proposition</span> <span m="477700">by a</span> <span m="477980">chain</span> <span m="481890">of</span> <span m="482080">logical</span> <span m="482650">deductions</span> <span m="491070">from a</span> <span m="491490">set</span> <span m="495930">of</span> <span m="496080">axioms.</span> </p>
<p><span m="502030">Now,</span> <span m="502370">that's</span> <span m="502590">a</span> <span m="502630">bit</span> <span m="502780">of</span> <span m="502850">a</span> <span m="502920">mouthful.</span> <span m="504070">There's</span> <span m="504330">three</span> <span m="505390">important</span> <span m="505930">components</span> <span m="506510">here--</span> <span m="508500">propositions,</span> <span m="510340">logical</span> <span m="510810">deductions,</span> <span m="512020">and</span> <span m="512640">axioms.</span> <span m="514780">And</span> <span m="514900">we're</span> <span m="515000">going</span> <span m="515090">to</span> <span m="515169">spend</span> <span m="516370">the</span> <span m="516450">rest</span> <span m="516700">of</span> <span m="516740">the</span> <span m="516830">class</span> <span m="517130">today</span> <span m="517429">talking</span> <span m="517780">about</span> <span m="518020">each</span> <span m="518240">of</span> <span m="518330">these,</span> <span m="518770">and then</span> <span m="518870">give</span> <span m="519000">an</span> <span m="519070">example</span> <span m="519460">of</span> <span m="519549">a</span> <span m="519610">proof.</span> <span m="521419">We'll</span> <span m="521539">start</span> <span m="521840">with</span> <span m="521980">propositions.</span> </p>
<p><span m="526910">A</span> <span m="527010">proposition</span> <span m="532220">is</span> <span m="532420">a</span> <span m="532480">statement</span> <span m="537890">that</span> <span m="539000">is</span> <span m="539910">either</span> <span m="541420">true</span> <span m="543530">or</span> <span m="543720">false.</span> <span m="547130">You</span> <span m="547160">may</span> <span m="547340">not</span> <span m="547600">know</span> <span m="547820">which</span> <span m="548030">one,</span> <span m="549030">but</span> <span m="549190">it's</span> <span m="549310">one</span> <span m="549530">or</span> <span m="549580">the</span> <span m="549720">other.</span> <span m="550800">A</span> <span m="551180">simple</span> <span m="551640">example--</span> <span m="552790">2</span> <span m="552990">plus</span> <span m="553270">3</span> <span m="553840">equals</span> <span m="554160">5.</span> <span m="555310">Now,</span> <span m="555520">that's</span> <span m="555750">a</span> <span m="555810">true</span> <span m="556280">proposition.</span> </p>
<p><span m="558560">Here's</span> <span m="558940">one</span> <span m="559180">that's</span> <span m="559350">a</span> <span m="559400">little</span> <span m="559590">more</span> <span m="559800">interesting.</span> <span m="567450">For</span> <span m="567670">all</span> <span m="568660">n</span> <span m="570130">in</span> <span m="570290">the</span> <span m="570380">set</span> <span m="570670">of</span> <span m="570740">natural</span> <span m="571180">numbers,</span> <span m="572900">n</span> <span m="573180">squared</span> <span m="573750">plus</span> <span m="574100">n</span> <span m="574580">plus</span> <span m="574890">41</span> <span m="577060">is</span> <span m="577460">a</span> <span m="577830">prime</span> <span m="578290">number.</span> <span m="583930">I</span> <span m="584080">know</span> <span m="584210">I've</span> <span m="584340">used</span> <span m="584640">some</span> <span m="584680">notation</span> <span m="585340">here.</span> </p>
<p><span m="586520">This</span> <span m="586890">is--</span> <span m="587330">the</span> <span m="587460">upside</span> <span m="587800">down</span> <span m="588300">A</span> <span m="588810">is</span> <span m="589180">the</span> <span m="589410">for</span> <span m="589760">all</span> <span m="590060">symbol.</span> <span m="593200">How</span> <span m="593310">many</span> <span m="593500">people</span> <span m="593740">have</span> <span m="593840">not</span> <span m="594180">seen</span> <span m="594380">that</span> <span m="594600">symbol</span> <span m="594860">before?</span> <span m="596620">A</span> <span m="596670">bunch</span> <span m="596930">of</span> <span m="596990">you.</span> <span m="597310">You're going</span> <span m="597390">to</span> <span m="597460">see</span> <span m="597620">a</span> <span m="597660">bunch</span> <span m="597880">of</span> <span m="597940">symbols</span> <span m="598310">here</span> <span m="599090">first</span> <span m="599270">week.</span> </p>
<p><span m="600110">And</span> <span m="600240">that</span> <span m="600380">means</span> <span m="600710">for</span> <span m="601020">every</span> <span m="601480">possible</span> <span m="601980">choice</span> <span m="602410">of</span> <span m="602550">n--</span> <span m="603520">and</span> <span m="603660">this</span> <span m="603850">is</span> <span m="604060">in</span> <span m="604210">the</span> <span m="604310">natural</span> <span m="604750">numbers,</span> <span m="605300">which</span> <span m="605610">is</span> <span m="606510">the</span> <span m="606620">set</span> <span m="607610">0,</span> <span m="607810">1,</span> <span m="608010">2,</span> <span m="608410">3,</span> <span m="610770">and</span> <span m="611000">so</span> <span m="611280">forth.</span> <span m="611970">It's</span> <span m="612120">the</span> <span m="612200">natural</span> <span m="612710">numbers.</span> <span m="613890">It's</span> <span m="614040">basically the</span> <span m="614510">integers,</span> <span m="614940">but</span> <span m="615070">not</span> <span m="615290">negative.</span> </p>
<p><span m="619570">So</span> <span m="619760">we're</span> <span m="619860">saying</span> <span m="620260">for</span> <span m="620480">every</span> <span m="620950">natural</span> <span m="621440">number,</span> <span m="621830">i.e.</span> <span m="622270">for</span> <span m="622450">0,</span> <span m="622790">for</span> <span m="622910">1,</span> <span m="623200">for</span> <span m="623350">2, and for</span> <span m="623760">3,</span> <span m="623940">and</span> <span m="624050">so</span> <span m="624230">forth,</span> <span m="625480">this</span> <span m="625950">expression</span> <span m="626700">is</span> <span m="626850">a</span> <span m="626920">prime.</span> <span m="627540">Now,</span> <span m="627720">a</span> <span m="627800">prime</span> <span m="628300">number</span> <span m="629280">is</span> <span m="629430">a</span> <span m="629490">number</span> <span m="630300">that</span> <span m="630410">is</span> <span m="630550">not</span> <span m="631190">divisible</span> <span m="632970">by</span> <span m="633200">any</span> <span m="633500">other</span> <span m="633670">number</span> <span m="633900">besides</span> <span m="634350">itself</span> <span m="634770">and</span> <span m="634910">1.</span> <span m="635830">So</span> <span m="636040">1,</span> <span m="636440">3,</span> <span m="636950">5,</span> <span m="637910">7</span> <span m="638280">are</span> <span m="638340">prime.</span> <span m="638850">9</span> <span m="639160">is</span> <span m="639320">not</span> <span m="639650">because</span> <span m="639800">it's</span> <span m="639930">3</span> <span m="640090">times</span> <span m="640360">3.</span> </p>
<p><span m="641890">Now,</span> <span m="642140">this</span> <span m="642410">part</span> <span m="642670">here</span> <span m="644670">is</span> <span m="644820">called</span> <span m="645220">the</span> <span m="645290">predicate.</span> <span m="649390">And</span> <span m="649520">a</span> <span m="649570">predicate</span> <span m="650220">is</span> <span m="650400">a</span> <span m="650480">proposition</span> <span m="655200">whose</span> <span m="655430">truth</span> <span m="660420">depends</span> <span m="663130">on</span> <span m="663440">the</span> <span m="663500">value</span> <span m="663940">of</span> <span m="664030">a</span> <span m="664090">variable--</span> <span m="670230">in</span> <span m="670310">this</span> <span m="670480">case,</span> <span m="670790">n.</span> <span m="676780">All right,</span> <span m="677130">this</span> <span m="677500">is</span> <span m="677650">referred</span> <span m="678120">to</span> <span m="678890">as</span> <span m="679130">the</span> <span m="679240">universe</span> <span m="679930">of</span> <span m="680140">discourse.</span> <span m="681480">It's</span> <span m="681690">the</span> <span m="681800">space</span> <span m="682290">of</span> <span m="682390">all</span> <span m="682680">the</span> <span m="682780">things</span> <span m="683000">we're</span> <span m="683130">talking</span> <span m="683540">about.</span> <span m="684240">We're</span> <span m="684520">only</span> <span m="684850">talking</span> <span m="685230">about</span> <span m="685450">natural</span> <span m="685800">numbers</span> <span m="686590">here.</span> <span m="688230">This</span> <span m="688350">is</span> <span m="688450">called</span> <span m="688760">a</span> <span m="688840">quantifier.</span> <span m="690140">We'll</span> <span m="690270">see</span> <span m="690440">more</span> <span m="690770">quantifiers</span> <span m="691510">later.</span> </p>
<p><span m="694620">All</span> <span m="694690">right,</span> <span m="694920">now</span> <span m="695070">to</span> <span m="695160">see</span> <span m="695860">if</span> <span m="697030">this</span> <span m="697400">proposition</span> <span m="698150">is</span> <span m="698260">true,</span> <span m="699820">we</span> <span m="700000">need</span> <span m="700230">to</span> <span m="700370">make</span> <span m="700560">sure</span> <span m="700900">that</span> <span m="701850">this</span> <span m="702430">predicate</span> <span m="702980">is</span> <span m="703120">true</span> <span m="703520">for</span> <span m="703800">every</span> <span m="704270">natural</span> <span m="704710">number</span> <span m="705070">n.</span> <span m="706770">So</span> <span m="706970">let's</span> <span m="707190">see</span> <span m="707310">if</span> <span m="707430">we</span> <span m="707520">can</span> <span m="708770">check</span> <span m="709090">that.</span> <span m="711160">Let's</span> <span m="711320">try</span> <span m="711530">some</span> <span m="711710">values.</span> </p>
<p><span m="713140">So</span> <span m="713410">we'll</span> <span m="713500">try</span> <span m="714510">n</span> <span m="714730">is</span> <span m="714840">1,</span> <span m="715230">2,</span> <span m="716340">3,</span> <span m="716770">and</span> <span m="717120">so</span> <span m="717350">forth.</span> <span m="718230">And</span> <span m="718510">we'll</span> <span m="718630">compute</span> <span m="719070">n</span> <span m="719220">squared</span> <span m="719690">plus</span> <span m="720360">n</span> <span m="720690">plus</span> <span m="720990">41.</span> <span m="722390">And then</span> <span m="722500">we'll</span> <span m="722610">check,</span> <span m="722970">is</span> <span m="723170">it</span> <span m="723290">prime?</span> <span m="725890">So</span> <span m="726220">for</span> <span m="726440">n</span> <span m="726650">equals</span> <span m="727030">0,</span> <span m="728680">n</span> <span m="728910">squared</span> <span m="729200">plus</span> <span m="729430">n</span> <span m="729560">plus</span> <span m="729740">41</span> <span m="730380">is</span> <span m="730560">41.</span> <span m="732202">Is</span> <span m="732680">41</span> <span m="733120">prime?</span> <span m="736390">Yeah,</span> <span m="737330">nothing</span> <span m="737610">divides</span> <span m="737960">41</span> <span m="738480">but</span> <span m="738580">itself</span> <span m="738970">and</span> <span m="739100">1.</span> </p>
<p><span m="741980">All right, let's</span> <span m="742130">try</span> <span m="742310">1.</span> <span m="743120">1</span> <span m="743410">squared</span> <span m="743660">plus</span> <span m="743870">1</span> <span m="744020">plus</span> <span m="744130">41</span> <span m="744500">is</span> <span m="744590">43.</span> <span m="745845">Is</span> <span m="746170">43</span> <span m="746680">prime?</span> <span m="748120">Yes.</span> <span m="750400">Let's</span> <span m="750600">try</span> <span m="750920">2.</span> <span m="752050">We</span> <span m="752460">get</span> <span m="752750">4</span> <span m="753330">plus</span> <span m="753610">2</span> <span m="753750">is</span> <span m="753840">6</span> <span m="754330">plus</span> <span m="754840">41 is</span> <span m="755210">47.</span> <span m="756440">Is</span> <span m="756870">47</span> <span m="757480">prime?</span> </p>
<p><span m="758230">AUDIENCE: Yes.</span> </p>
<p><span m="759030">PROFESSOR: Yes.</span> <span m="760650">Looking</span> <span m="760820">good.</span> <span m="761200">3--</span> <span m="761720">I</span> <span m="761780">got</span> <span m="762440">9,</span> <span m="763330">12,</span> <span m="765110">53.</span> <span m="766640">Is 53</span> <span m="767120">prime?</span> <span m="768600">Yeah.</span> <span m="770000">And</span> <span m="770230">I</span> <span m="770290">could</span> <span m="770660">keep</span> <span m="770890">on</span> <span m="771060">going</span> <span m="771430">here.</span> <span m="771810">I</span> <span m="771860">could</span> <span m="772090">go</span> <span m="772210">down</span> <span m="772360">to</span> <span m="772450">20.</span> <span m="773550">I</span> <span m="773700">get</span> <span m="774260">420--</span> <span m="776060">461.</span> <span m="777140">In</span> <span m="777620">fact,</span> <span m="778040">that</span> <span m="778200">is</span> <span m="778310">a</span> <span m="778370">prime.</span> <span m="780150">And</span> <span m="780230">I</span> <span m="780290">could</span> <span m="780420">just</span> <span m="780590">keep</span> <span m="780780">on</span> <span m="780950">going</span> <span m="781290">here.</span> <span m="782410">Go</span> <span m="782530">down</span> <span m="782690">to</span> <span m="782770">39.</span> <span m="783460">I</span> <span m="783510">get</span> <span m="784250">1,601.</span> <span m="787020">You</span> <span m="787120">can</span> <span m="787250">check.</span> <span m="787550">That</span> <span m="787740">is</span> <span m="787850">a</span> <span m="787920">prime.</span> </p>
<p><span m="789880">The</span> <span m="789980">first</span> <span m="790280">40</span> <span m="790550">values</span> <span m="790960">of</span> <span m="791050">n,</span> <span m="792100">the</span> <span m="792190">proposition</span> <span m="792810">is</span> <span m="792930">true.</span> <span m="793120">The</span> <span m="793220">predicate</span> <span m="793570">is</span> <span m="793680">true.</span> <span m="794700">It is</span> <span m="795060">prime.</span> <span m="796640">Now,</span> <span m="797800">this</span> <span m="798000">is</span> <span m="798090">a</span> <span m="798170">great</span> <span m="798530">example</span> <span m="798970">because</span> <span m="799360">in</span> <span m="799440">a</span> <span m="799500">lot</span> <span m="799780">of</span> <span m="799890">fields--</span> <span m="800520">physics,</span> <span m="801290">for</span> <span m="801460">example;</span> <span m="801900">statistics,</span> <span m="802460">often--</span> <span m="805430">you</span> <span m="805560">checked</span> <span m="805810">40</span> <span m="806190">examples.</span> <span m="806720">That's</span> <span m="806990">above</span> <span m="807310">and</span> <span m="807410">beyond</span> <span m="807690">the</span> <span m="807750">call</span> <span m="808030">of</span> <span m="808110">duty.</span> <span m="809040">It's</span> <span m="809210">always</span> <span m="809570">true.</span> <span m="810820">So</span> <span m="810990">yeah,</span> <span m="811220">this</span> <span m="811390">must</span> <span m="811610">be</span> <span m="811700">true,</span> <span m="812530">right?</span> </p>
<p><span m="815160">No,</span> <span m="816540">wrong.</span> <span m="817730">Often,</span> <span m="818070">you'll</span> <span m="818220">see</span> <span m="818930">this</span> <span m="819150">in</span> <span m="819210">a</span> <span m="819270">lot</span> <span m="819490">of</span> <span m="819660">scientific</span> <span m="820170">fields.</span> <span m="820940">It</span> <span m="821060">is</span> <span m="821220">not</span> <span m="821450">true.</span> <span m="821690">Can</span> <span m="821960">anybody</span> <span m="822090">give</span> <span m="822280">me</span> <span m="822370">an</span> <span m="822430">example</span> <span m="822850">of</span> <span m="822960">n</span> <span m="823220">for</span> <span m="823330">which</span> <span m="823995">n</span> <span m="824260">squared</span> <span m="824690">plus</span> <span m="824920">n</span> <span m="825040">plus</span> <span m="825180">41</span> <span m="825640">is</span> <span m="825860">not</span> <span m="826160">prime?</span> <span m="826750">Yeah?</span> </p>
<p><span m="827390">AUDIENCE: 40.</span> </p>
<p><span m="828270">PROFESSOR: 40,</span> <span m="829370">good.</span> <span m="829720">Let's</span> <span m="829950">see</span> <span m="830090">about</span> <span m="830380">40.</span> <span m="831720">40</span> <span m="832370">squared</span> <span m="832960">plus</span> <span m="833270">40</span> <span m="833910">plus</span> <span m="834220">41</span> <span m="836410">is</span> <span m="836810">1,681.</span> <span m="839990">What's</span> <span m="840150">that</span> <span m="840300">equal?</span> <span m="842960">41</span> <span m="843530">squared.</span> <span m="846070">So</span> <span m="846280">it</span> <span m="846340">is</span> <span m="846520">not</span> <span m="846730">prime.</span> <span m="847740">Somebody</span> <span m="848040">give</span> <span m="848210">me</span> <span m="848330">an</span> <span m="848550">obvious</span> <span m="849170">example</span> <span m="849650">where</span> <span m="849860">it's</span> <span m="849990">not</span> <span m="850240">prime.</span> </p>
<p><span m="850830">AUDIENCE: 41.</span> </p>
<p><span m="851530">PROFESSOR: 41--</span> <span m="852400">yeah,</span> <span m="852610">41</span> <span m="853080">squared,</span> <span m="853330">we get</span> <span m="853720">everything</span> <span m="854050">is</span> <span m="854120">divided</span> <span m="854360">by</span> <span m="854460">41.</span> <span m="855480">But</span> <span m="855790">40</span> <span m="856130">is</span> <span m="856250">the</span> <span m="856340">first</span> <span m="856590">break-point.</span> <span m="857990">So</span> <span m="858350">the</span> <span m="858430">first</span> <span m="858920">40</span> <span m="859500">examples</span> <span m="860010">work,</span> <span m="860450">and</span> <span m="860740">then</span> <span m="860980">it</span> <span m="861130">failed.</span> <span m="862110">So</span> <span m="862270">this</span> <span m="862500">proposition</span> <span m="863730">is</span> <span m="864130">false,</span> <span m="866150">even</span> <span m="866340">though</span> <span m="866500">it</span> <span m="866570">was</span> <span m="866700">looking</span> <span m="867320">pretty</span> <span m="867570">good.</span> </p>
<p><span m="869040">There's</span> <span m="869090">a</span> <span m="869160">reason</span> <span m="869470">I'm</span> <span m="869570">doing</span> <span m="869820">this.</span> <span m="869990">In fact,</span> <span m="870130">I'm going</span> <span m="870230">to</span> <span m="870330">do</span> <span m="870480">it</span> <span m="870560">some</span> <span m="870680">more</span> <span m="870910">here.</span> <span m="871990">I'm going</span> <span m="872120">to</span> <span m="872200">beat you</span> <span m="872570">over</span> <span m="872700">the</span> <span m="872790">head</span> <span m="872970">with</span> <span m="873120">it.</span> <span m="875000">Here's</span> <span m="875280">a</span> <span m="876170">famous</span> <span m="876610">in</span> <span m="876710">mathematics</span> <span m="878920">statement.</span> <span m="881880">a</span> <span m="882090">to</span> <span m="882160">the</span> <span m="882300">fourth</span> <span m="882920">plus</span> <span m="883290">b</span> <span m="883620">to</span> <span m="883700">the</span> <span m="883830">fourth</span> <span m="884490">plus</span> <span m="885640">c</span> <span m="885980">to</span> <span m="886050">the</span> <span m="886160">fourth</span> <span m="887380">equals</span> <span m="887820">d</span> <span m="888030">to</span> <span m="888110">the</span> <span m="888210">fourth</span> <span m="890090">has</span> <span m="891070">no</span> <span m="892430">positive</span> <span m="895620">integer</span> <span m="898710">solutions.</span> <span m="901200">That</span> <span m="901400">is</span> <span m="901530">a</span> <span m="901600">proposition.</span> </p>
<p><span m="902980">Now,</span> <span m="903440">this</span> <span m="903760">proposition</span> <span m="904510">was</span> <span m="904680">conjectured</span> <span m="905390">to</span> <span m="905450">be</span> <span m="905570">true</span> <span m="905930">by</span> <span m="906190">Euler</span> <span m="907160">in</span> <span m="907280">1769.</span> <span m="909740">Euler's</span> <span m="910100">a</span> <span m="910150">big</span> <span m="910340">honcho</span> <span m="910750">in</span> <span m="910830">math.</span> <span m="911570">We</span> <span m="911820">still</span> <span m="912030">talk</span> <span m="912250">about</span> <span m="912430">him</span> <span m="912510">a</span> <span m="912570">lot</span> <span m="912990">even</span> <span m="913160">though</span> <span m="913310">he's</span> <span m="913970">been</span> <span m="914110">dead</span> <span m="914330">for</span> <span m="914450">centuries.</span> <span m="916700">It</span> <span m="916870">was</span> <span m="917210">unsolved</span> <span m="918130">for</span> <span m="918370">over</span> <span m="918560">2</span> <span m="918660">centuries.</span> <span m="920100">Mathematicians</span> <span m="920740">worked</span> <span m="921000">on</span> <span m="921270">it.</span> </p>
<p><span m="921890">It</span> <span m="922000">was</span> <span m="922170">finally</span> <span m="922610">disapproved</span> <span m="923300">by</span> <span m="923780">a</span> <span m="924270">very</span> <span m="924530">clever</span> <span m="924920">fellow</span> <span m="925280">named</span> <span m="925560">Noam</span> <span m="925880">Elkies</span> <span m="927680">218</span> <span m="928310">years</span> <span m="928560">later</span> <span m="928980">after</span> <span m="929250">it was</span> <span m="929370">conjectured.</span> <span m="930090">He</span> <span m="930330">worked</span> <span m="930580">at</span> <span m="930650">that</span> <span m="930850">other</span> <span m="931090">school</span> <span m="932210">down</span> <span m="932510">the</span> <span m="932580">street.</span> <span m="934100">And</span> <span m="935250">he</span> <span m="935480">came</span> <span m="935740">up</span> <span m="935870">with</span> <span m="935980">this.</span> <span m="937200">a</span> <span m="937560">equals</span> <span m="938730">95,800.</span> <span m="941990">b</span> <span m="942440">equals</span> <span m="942980">217,519.</span> <span m="946510">c</span> <span m="946800">equals</span> <span m="947120">414,560.</span> <span m="950330">You</span> <span m="950440">don't</span> <span m="950550">have</span> <span m="950620">to</span> <span m="950710">remember</span> <span m="951080">these</span> <span m="951310">numbers.</span> <span m="951620">We're</span> <span m="951740">not</span> <span m="951930">going</span> <span m="952050">to</span> <span m="952820">quiz</span> <span m="953105">you on</span> <span m="953390">that--</span> <span m="954050">422,481.</span> </p>
<p><span m="957500">Now,</span> <span m="957600">he</span> <span m="957760">claims--</span> <span m="958190">I've</span> <span m="958320">never</span> <span m="958540">personally</span> <span m="959010">checked it,</span> <span m="959300">but presumably,</span> <span m="959760">people</span> <span m="959990">have--</span> <span m="960640">you</span> <span m="960790">plug</span> <span m="961060">those</span> <span m="961310">in</span> <span m="961460">here,</span> <span m="962360">and</span> <span m="962490">you</span> <span m="962550">have</span> <span m="962770">an</span> <span m="962840">equality.</span> <span m="964580">So</span> <span m="964660">he</span> <span m="964720">says.</span> <span m="965850">So</span> <span m="966090">in</span> <span m="966190">fact,</span> <span m="966920">the</span> <span m="967190">correct</span> <span m="967700">proposition</span> <span m="968340">is</span> <span m="969280">there</span> <span m="969410">does</span> <span m="969610">exist</span> <span m="970820">a,</span> <span m="971320">b,</span> <span m="971820">c,</span> <span m="972320">d</span> <span m="974170">in</span> <span m="974550">the</span> <span m="974730">positive</span> <span m="975520">natural</span> <span m="975980">numbers</span> <span m="977450">such</span> <span m="977510">that</span> <span m="977880">a</span> <span m="977960">the</span> <span m="978070">fourth</span> <span m="978500">plus</span> <span m="978770">b</span> <span m="978970">to</span> <span m="979030">the</span> <span m="979160">fourth</span> <span m="979610">plus</span> <span m="980000">c</span> <span m="980090">to</span> <span m="980150">the</span> <span m="980280">fourth</span> <span m="981000">equals</span> <span m="981350">d</span> <span m="981520">to</span> <span m="981580">the</span> <span m="981710">fourth.</span> </p>
<p><span m="983510">I</span> <span m="983560">used</span> <span m="983850">a</span> <span m="983890">new</span> <span m="984070">quantifier</span> <span m="984770">here</span> <span m="986020">called</span> <span m="986590">there</span> <span m="986910">exists.</span> <span m="988460">Instead</span> <span m="988690">of</span> <span m="988770">an</span> <span m="988850">upside</span> <span m="989230">down</span> <span m="989510">A,</span> <span m="989700">it's</span> <span m="989870">a</span> <span m="989910">backwards</span> <span m="990380">E.</span> <span m="990660">Don't</span> <span m="991030">ask</span> <span m="991300">me</span> <span m="991410">why.</span> <span m="993030">That's</span> <span m="993280">what</span> <span m="993410">it</span> <span m="993490">is.</span> </p>
<p><span m="995960">The</span> <span m="996070">plus</span> <span m="996740">means</span> <span m="997690">you</span> <span m="997810">can't</span> <span m="998040">have</span> <span m="998550">0</span> <span m="998970">or</span> <span m="999140">negative</span> <span m="999460">numbers.</span> <span m="1000040">So</span> <span m="1000200">these are</span> <span m="1000575">the</span> <span m="1000950">positive</span> <span m="1001460">natural</span> <span m="1001790">numbers.</span> <span m="1005750">And</span> <span m="1005960">here's</span> <span m="1006210">your</span> <span m="1006320">predicate,</span> <span m="1009790">which</span> <span m="1009960">of</span> <span m="1010100">course,</span> <span m="1010410">the</span> <span m="1010510">truth</span> <span m="1010810">of</span> <span m="1010890">this</span> <span m="1011080">depends</span> <span m="1011460">on</span> <span m="1011550">the</span> <span m="1011620">values</span> <span m="1012030">of</span> <span m="1012130">a, b, c</span> <span m="1012630">and</span> <span m="1012740">d.</span> <span m="1015040">It took</span> <span m="1015500">a</span> <span m="1015540">long</span> <span m="1015820">time</span> <span m="1016130">to</span> <span m="1016200">figure</span> <span m="1016500">out</span> <span m="1016660">that</span> <span m="1016740">actually,</span> <span m="1017080">there</span> <span m="1017200">was</span> <span m="1017610">a</span> <span m="1017670">solution</span> <span m="1018130">here.</span> <span m="1019100">Obviously,</span> <span m="1019470">everything</span> <span m="1019710">they</span> <span m="1019790">tried</span> <span m="1020020">until</span> <span m="1020160">that</span> <span m="1020230">time</span> <span m="1020530">failed.</span> </p>
<p><span m="1021150">Let</span> <span m="1021270">me</span> <span m="1021380">give</span> <span m="1021520">you</span> <span m="1021620">another</span> <span m="1021950">one.</span> <span m="1028300">313</span> <span m="1030780">x</span> <span m="1031119">cubed</span> <span m="1031560">plus</span> <span m="1031880">y</span> <span m="1032180">cubed</span> <span m="1034020">equals</span> <span m="1034420">z</span> <span m="1034700">cubed</span> <span m="1036420">has</span> <span m="1037460">no</span> <span m="1038230">positive</span> <span m="1042630">integer</span> <span m="1044220">solutions.</span> <span m="1049530">This</span> <span m="1049720">turns</span> <span m="1049950">out</span> <span m="1050070">to</span> <span m="1050130">be</span> <span m="1050250">false.</span> <span m="1051850">But</span> <span m="1052040">the</span> <span m="1052130">shortest,</span> <span m="1052910">smallest</span> <span m="1053680">counter-example</span> <span m="1054580">has</span> <span m="1054710">over</span> <span m="1054960">1,000</span> <span m="1055850">digits.</span> <span m="1057950">This</span> <span m="1058130">one</span> <span m="1058250">was</span> <span m="1058410">easy.</span> <span m="1058770">It only has</span> <span m="1058960">six</span> <span m="1059280">digits.</span> <span m="1060650">So</span> <span m="1060790">there's</span> <span m="1060980">no</span> <span m="1061250">way</span> <span m="1061490">ever</span> <span m="1061940">you'd use</span> <span m="1062320">a</span> <span m="1062390">computer</span> <span m="1063560">to</span> <span m="1063680">exhaustively</span> <span m="1064330">search</span> <span m="1064660">1,000</span> <span m="1065190">digit</span> <span m="1065700">numbers</span> <span m="1066090">here</span> <span m="1066600">to</span> <span m="1066680">show</span> <span m="1066900">it's</span> <span m="1067060">false.</span> </p>
<p><span m="1069440">Now,</span> <span m="1069540">of</span> <span m="1069640">course,</span> <span m="1069820">some</span> <span m="1069880">of</span> <span m="1069950">you are</span> <span m="1070080">probably</span> <span m="1070470">thinking,</span> <span m="1072620">why</span> <span m="1073090">on</span> <span m="1073330">earth</span> <span m="1073810">would</span> <span m="1074130">I</span> <span m="1074210">care</span> <span m="1075690">if</span> <span m="1075890">313</span> <span m="1077070">times</span> <span m="1077370">x</span> <span m="1077590">cubed</span> <span m="1077780">plus</span> <span m="1077970">y</span> <span m="1078180">cubed</span> <span m="1078520">equals</span> <span m="1078860">z</span> <span m="1079070">cubed</span> <span m="1079590">has</span> <span m="1080790">a</span> <span m="1080870">solution?</span> <span m="1082670">And</span> <span m="1082810">that</span> <span m="1082860">probably</span> <span m="1083220">won't</span> <span m="1083430">be</span> <span m="1083510">the</span> <span m="1083610">last</span> <span m="1083960">time</span> <span m="1084150">that</span> <span m="1084350">thought</span> <span m="1084550">occurs</span> <span m="1084910">to</span> <span m="1084980">you</span> <span m="1085430">during</span> <span m="1085650">the</span> <span m="1085740">term.</span> <span m="1087310">And</span> <span m="1087590">why</span> <span m="1088040">on</span> <span m="1088130">earth</span> <span m="1088280">would</span> <span m="1088420">anybody</span> <span m="1089240">ever</span> <span m="1089530">try to</span> <span m="1089740">even</span> <span m="1089990">find</span> <span m="1090430">a</span> <span m="1090490">solution</span> <span m="1091060">to</span> <span m="1091140">that?</span> <span m="1093320">I mean,</span> <span m="1093450">mathematicians</span> <span m="1094140">are</span> <span m="1094240">sort of a</span> <span m="1094360">rare</span> <span m="1094700">breed.</span> </p>
<p><span m="1095830">Now,</span> <span m="1096250">actually</span> <span m="1096640">in</span> <span m="1096690">this</span> <span m="1096870">case,</span> <span m="1098140">that's</span> <span m="1098430">really</span> <span m="1098710">important</span> <span m="1099240">in</span> <span m="1099300">practice.</span> <span m="1102580">This</span> <span m="1102700">equation</span> <span m="1103370">is</span> <span m="1103500">an</span> <span m="1103570">example</span> <span m="1104090">of</span> <span m="1104190">what's</span> <span m="1104280">called</span> <span m="1104590">an</span> <span m="1104870">elliptic</span> <span m="1105010">curve--</span> <span m="1105690">elliptic</span> <span m="1105950">curve.</span> <span m="1106300">You</span> <span m="1106400">study</span> <span m="1106740">these</span> <span m="1107850">if you're</span> <span m="1107990">really</span> <span m="1108230">a</span> <span m="1108290">specialist</span> <span m="1109050">in</span> <span m="1109260">mathematics</span> <span m="1109820">in</span> <span m="1109880">graduate</span> <span m="1110310">school,</span> <span m="1111400">or</span> <span m="1111640">if</span> <span m="1111700">you</span> <span m="1111820">work</span> <span m="1112030">for</span> <span m="1112150">certain</span> <span m="1112870">three-letter</span> <span m="1113290">agencies</span> <span m="1114770">because</span> <span m="1115110">it's</span> <span m="1115380">central</span> <span m="1115880">to</span> <span m="1115990">the</span> <span m="1116130">understanding</span> <span m="1116860">of</span> <span m="1116920">how</span> <span m="1117140">to</span> <span m="1117230">factor</span> <span m="1117670">large</span> <span m="1118030">integers.</span> <span m="1119670">That</span> <span m="1119770">means</span> <span m="1120920">factoring,</span> <span m="1121440">showing</span> <span m="1121900">that--</span> <span m="1122760">what</span> <span m="1123180">was</span> <span m="1123450">it--</span> <span m="1123760">1,681</span> <span m="1124870">is</span> <span m="1125000">41</span> <span m="1125470">times</span> <span m="1125710">41.</span> </p>
<p><span m="1126916">And I</span> <span m="1127320">said, OK,</span> <span m="1127800">who</span> <span m="1128000">cares</span> <span m="1128350">about</span> <span m="1128610">factoring?</span> <span m="1130380">Well,</span> <span m="1130520">factoring</span> <span m="1132000">is</span> <span m="1132190">the</span> <span m="1132300">way</span> <span m="1132680">to</span> <span m="1133040">break</span> <span m="1133990">cryptosystems</span> <span m="1134880">like</span> <span m="1135090">RSA,</span> <span m="1137050">which</span> <span m="1137330">are</span> <span m="1137490">used</span> <span m="1137980">for</span> <span m="1138150">everything</span> <span m="1138625">that</span> <span m="1139100">we</span> <span m="1139280">do</span> <span m="1139480">electronically</span> <span m="1140090">today.</span> <span m="1141840">You</span> <span m="1142100">have</span> <span m="1142210">a</span> <span m="1142280">Paypal</span> <span m="1142750">account.</span> <span m="1143130">You</span> <span m="1143220">buy</span> <span m="1143430">something</span> <span m="1143760">online.</span> <span m="1144230">You're</span> <span m="1144320">using</span> <span m="1144650">SSL.</span> <span m="1145710">They're</span> <span m="1145900">all</span> <span m="1146190">using</span> <span m="1146510">cryptosystems,</span> <span m="1148160">almost</span> <span m="1148450">all of</span> <span m="1148600">which</span> <span m="1148750">are</span> <span m="1148790">based</span> <span m="1149050">on</span> <span m="1149150">number</span> <span m="1149400">theory.</span> <span m="1150400">And</span> <span m="1150640">in</span> <span m="1150960">particular,</span> <span m="1151350">they're</span> <span m="1151460">based</span> <span m="1151740">on</span> <span m="1151860">factoring.</span> <span m="1153130">And</span> <span m="1153260">if</span> <span m="1153320">you</span> <span m="1153460">can</span> <span m="1153620">find</span> <span m="1153890">good</span> <span m="1154060">solutions</span> <span m="1154700">to</span> <span m="1154820">things</span> <span m="1155120">like</span> <span m="1155340">this,</span> <span m="1156570">or</span> <span m="1156790">solutions</span> <span m="1157370">to</span> <span m="1157460">things</span> <span m="1157680">like</span> <span m="1157850">this,</span> <span m="1158610">all</span> <span m="1158810">of</span> <span m="1158890">a</span> <span m="1158940">sudden,</span> <span m="1159260">you</span> <span m="1159390">can</span> <span m="1159520">get</span> <span m="1160480">an</span> <span m="1160630">angle</span> <span m="1161110">and</span> <span m="1161190">a</span> <span m="1161250">wedge</span> <span m="1161660">on</span> <span m="1161830">factoring.</span> </p>
<p><span m="1163500">And</span> <span m="1163610">it's</span> <span m="1163710">because</span> <span m="1164030">of</span> <span m="1164090">that</span> <span m="1164330">that</span> <span m="1164470">now</span> <span m="1164700">RSA</span> <span m="1166510">uses</span> <span m="1167040">1,000</span> <span m="1167720">digit</span> <span m="1168670">moduluses</span> <span m="1169610">instead</span> <span m="1169970">of</span> <span m="1170600">hundred</span> <span m="1170940">digit</span> <span m="1171240">moduluses</span> <span m="1171830">like</span> <span m="1171980">they</span> <span m="1172090">used</span> <span m="1172290">to</span> <span m="1172360">use,</span> <span m="1173070">because</span> <span m="1173330">people</span> <span m="1173560">figured</span> <span m="1173830">out</span> <span m="1173950">how</span> <span m="1174050">to</span> <span m="1174140">factor</span> <span m="1174510">and</span> <span m="1174580">how</span> <span m="1174710">to</span> <span m="1174780">break</span> <span m="1175290">the</span> <span m="1175370">cryptosystem.</span> <span m="1176430">If</span> <span m="1176740">you</span> <span m="1176940">could</span> <span m="1177060">break</span> <span m="1177460">those</span> <span m="1177670">cryptosystems,</span> <span m="1179490">well, you</span> <span m="1179610">can't</span> <span m="1179860">rule</span> <span m="1180110">the</span> <span m="1180190">world,</span> <span m="1180540">but</span> <span m="1180640">it's</span> <span m="1180760">close.</span> </p>
<p><span m="1182350">All</span> <span m="1182450">right,</span> <span m="1182690">so</span> <span m="1183340">we'll</span> <span m="1183550">talk</span> <span m="1183780">more</span> <span m="1184000">about</span> <span m="1184290">this</span> <span m="1184950">the</span> <span m="1185110">week</span> <span m="1185300">after</span> <span m="1185510">next</span> <span m="1185850">when we</span> <span m="1186030">do</span> <span m="1186200">number</span> <span m="1186460">theory,</span> <span m="1186830">and</span> <span m="1187560">we</span> <span m="1187740">work</span> <span m="1187990">up</span> <span m="1188120">to</span> <span m="1188210">RSA</span> <span m="1188540">and</span> <span m="1188800">how</span> <span m="1188940">that</span> <span m="1189090">cryptosystem</span> <span m="1189680">works,</span> <span m="1190020">and</span> <span m="1190110">why</span> <span m="1190280">factoring</span> <span m="1190770">is</span> <span m="1190860">so</span> <span m="1191010">important.</span> <span m="1192880">So</span> <span m="1193790">yeah,</span> <span m="1193970">you</span> <span m="1194290">don't</span> <span m="1194450">have</span> <span m="1194560">to</span> <span m="1195260">really</span> <span m="1195500">have</span> <span m="1195580">to</span> <span m="1195660">worry</span> <span m="1195850">about</span> <span m="1196100">this.</span> <span m="1196370">But</span> <span m="1196580">these</span> <span m="1196800">things</span> <span m="1197010">are</span> <span m="1197070">important.</span> </p>
<p><span m="1197470">And the</span> <span m="1197890">bigger</span> <span m="1198150">message</span> <span m="1199470">is</span> <span m="1199920">that</span> <span m="1200050">you</span> <span m="1200140">don't</span> <span m="1200550">just</span> <span m="1200750">try</span> <span m="1201010">a</span> <span m="1201100">few</span> <span m="1201310">cases,</span> <span m="1201750">and if</span> <span m="1201900">it</span> <span m="1201980">works,</span> <span m="1202300">you</span> <span m="1202380">think</span> <span m="1202970">it's</span> <span m="1203150">done.</span> <span m="1204610">That's</span> <span m="1205340">not</span> <span m="1205500">how</span> <span m="1205620">the</span> <span m="1205710">game</span> <span m="1206150">works</span> <span m="1206490">in</span> <span m="1206540">mathematics.</span> <span m="1207010">You can</span> <span m="1207110">get</span> <span m="1207290">an</span> <span m="1207390">idea</span> <span m="1207800">of</span> <span m="1207880">maybe</span> <span m="1208140">it's</span> <span m="1208280">true,</span> <span m="1209300">but</span> <span m="1209750">doesn't</span> <span m="1210490">tell</span> <span m="1210640">you</span> <span m="1210700">the</span> <span m="1210820">answer.</span> </p>
<p><span m="1213390">All</span> <span m="1213510">right,</span> <span m="1213700">let me</span> <span m="1213810">give you</span> <span m="1213920">another</span> <span m="1214220">one.</span> <span m="1215380">This</span> <span m="1215570">is</span> <span m="1215690">another</span> <span m="1216000">very</span> <span m="1216380">famous</span> <span m="1216740">one</span> <span m="1216900">that</span> <span m="1217030">probably</span> <span m="1217390">most of</span> <span m="1217680">you have</span> <span m="1217890">heard</span> <span m="1218100">of.</span> <span m="1219830">The</span> <span m="1219980">regions</span> <span m="1222730">in</span> <span m="1223140">any</span> <span m="1223400">map</span> <span m="1226520">can</span> <span m="1227440">be</span> <span m="1227780">colored</span> <span m="1231100">in</span> <span m="1231650">four</span> <span m="1232050">colors</span> <span m="1234880">so</span> <span m="1235170">that</span> <span m="1237110">adjacent</span> <span m="1237880">regions</span> <span m="1245170">have</span> <span m="1245920">different</span> <span m="1246320">colors.</span> <span m="1247710">Like</span> <span m="1247860">a</span> <span m="1247910">map</span> <span m="1248250">of</span> <span m="1248300">the</span> <span m="1248340">United</span> <span m="1248670">States--</span> <span m="1249270">every</span> <span m="1249480">state</span> <span m="1249750">gets</span> <span m="1249920">a</span> <span m="1249980">color.</span> <span m="1250860">If</span> <span m="1251080">two</span> <span m="1251270">states</span> <span m="1251630">share</span> <span m="1251910">a</span> <span m="1251950">border,</span> <span m="1252930">they</span> <span m="1253020">have</span> <span m="1253160">different</span> <span m="1253440">colors</span> <span m="1255100">so</span> <span m="1255200">you</span> <span m="1255270">can</span> <span m="1255380">distinguish</span> <span m="1255900">them.</span> </p>
<p><span m="1257430">This</span> <span m="1257520">is</span> <span m="1257650">known</span> <span m="1257900">as</span> <span m="1258000">the</span> <span m="1258090">four</span> <span m="1258360">color</span> <span m="1258730">theorem.</span> <span m="1259530">And</span> <span m="1259690">it's</span> <span m="1260060">very</span> <span m="1260490">famous</span> <span m="1260900">in the</span> <span m="1261020">popular</span> <span m="1261400">literature.</span> <span m="1262570">How</span> <span m="1262700">many</span> <span m="1262840">people</span> <span m="1263100">have</span> <span m="1263200">heard</span> <span m="1263310">of</span> <span m="1263360">this</span> <span m="1263840">theorem</span> <span m="1264000">before?</span> <span m="1265060">Yeah,</span> <span m="1265400">OK.</span> <span m="1265680">So</span> <span m="1265820">you've</span> <span m="1265960">all</span> <span m="1266200">heard</span> <span m="1266420">of</span> <span m="1266500">it.</span> </p>
<p><span m="1267340">It has</span> <span m="1267470">a</span> <span m="1267540">long</span> <span m="1267830">history.</span> <span m="1268250">It was</span> <span m="1268370">conjectured</span> <span m="1269210">by</span> <span m="1269740">somebody</span> <span m="1270000">named</span> <span m="1270280">Guthrie</span> <span m="1270790">in</span> <span m="1270880">1853.</span> <span m="1272240">He's</span> <span m="1272430">the</span> <span m="1272480">first</span> <span m="1272710">person</span> <span m="1272960">to</span> <span m="1273020">say</span> <span m="1273210">this</span> <span m="1273410">ought</span> <span m="1273530">to</span> <span m="1273590">be</span> <span m="1273720">possible.</span> <span m="1274950">And</span> <span m="1275120">there</span> <span m="1275210">were</span> <span m="1275320">many</span> <span m="1276370">false</span> <span m="1276870">proofs</span> <span m="1277720">over</span> <span m="1278750">the</span> <span m="1279140">ensuing</span> <span m="1279530">century.</span> </p>
<p><span m="1280630">One</span> <span m="1280830">of</span> <span m="1280880">the</span> <span m="1280950">most</span> <span m="1281500">convincing</span> <span m="1282060">was</span> <span m="1282200">a</span> <span m="1282270">proof</span> <span m="1282590">using</span> <span m="1282960">pictures</span> <span m="1283510">by</span> <span m="1283980">Kempe</span> <span m="1284940">in</span> <span m="1285070">1879,</span> <span m="1286980">26</span> <span m="1287500">years</span> <span m="1287710">later.</span> <span m="1288700">And</span> <span m="1288960">this</span> <span m="1289140">proof</span> <span m="1289390">was</span> <span m="1289530">believed</span> <span m="1290020">for</span> <span m="1290180">over</span> <span m="1290470">a</span> <span m="1290540">decade.</span> <span m="1291420">Mathematicians</span> <span m="1292110">thought</span> <span m="1292290">the</span> <span m="1292360">proof</span> <span m="1292610">was</span> <span m="1292730">right</span> <span m="1293890">until</span> <span m="1294140">another</span> <span m="1294400">mathematician</span> <span m="1295040">named</span> <span m="1295260">Heawood</span> <span m="1296320">found</span> <span m="1296570">a</span> <span m="1296610">fatal</span> <span m="1297020">flaw</span> <span m="1297640">in</span> <span m="1297740">the</span> <span m="1297870">argument.</span> </p>
<p><span m="1299270">Now,</span> <span m="1299350">this</span> <span m="1299570">proof</span> <span m="1300500">by</span> <span m="1300630">Kempe</span> <span m="1301030">consisted</span> <span m="1301510">of</span> <span m="1301570">drawing</span> <span m="1302000">pictures</span> <span m="1302590">of</span> <span m="1302690">what</span> <span m="1302900">maps</span> <span m="1303530">have</span> <span m="1303810">to</span> <span m="1303910">look</span> <span m="1304130">like.</span> <span m="1305250">So he</span> <span m="1305380">started by</span> <span m="1305400">saying,</span> <span m="1305560">a</span> <span m="1305620">map</span> <span m="1306370">has</span> <span m="1306620">to</span> <span m="1306710">look</span> <span m="1306910">like</span> <span m="1307060">one</span> <span m="1307210">of</span> <span m="1307260">these</span> <span m="1307460">types.</span> <span m="1307830">And he would</span> <span m="1307940">draw</span> <span m="1308490">pictures</span> <span m="1308850">of</span> <span m="1308950">them.</span> <span m="1309620">And</span> <span m="1309730">then</span> <span m="1309850">he</span> <span m="1309950">argued</span> <span m="1310910">that</span> <span m="1311050">those</span> <span m="1311600">types</span> <span m="1312030">that he</span> <span m="1312150">drew</span> <span m="1312290">pictures of,</span> <span m="1312690">it</span> <span m="1312940">worked</span> <span m="1313190">for.</span> </p>
<p><span m="1315580">Proofs</span> <span m="1315990">by</span> <span m="1316130">picture</span> <span m="1317340">are</span> <span m="1317530">often</span> <span m="1317910">very</span> <span m="1318310">convincing</span> <span m="1319460">and</span> <span m="1319650">very</span> <span m="1320070">wrong.</span> <span m="1321110">And</span> <span m="1321290">I'm</span> <span m="1321370">going</span> <span m="1321470">to</span> <span m="1321510">give</span> <span m="1321730">you</span> <span m="1321860">one</span> <span m="1322170">to</span> <span m="1322250">start</span> <span m="1322510">lecture</span> <span m="1322810">next</span> <span m="1323100">time.</span> <span m="1323550">It'll</span> <span m="1323840">be a</span> <span m="1323970">proof</span> <span m="1324220">by</span> <span m="1324340">PowerPoint,</span> <span m="1324930">which</span> <span m="1325080">is</span> <span m="1325180">even</span> <span m="1325340">worse</span> <span m="1325640">than</span> <span m="1325710">proof</span> <span m="1325910">by</span> <span m="1326030">picture.</span> <span m="1328130">And</span> <span m="1328330">it</span> <span m="1328530">is</span> <span m="1328650">compelling.</span> <span m="1331020">And</span> <span m="1331340">the</span> <span m="1331690">point</span> <span m="1331970">will to</span> <span m="1332010">be</span> <span m="1332100">to</span> <span m="1332160">show</span> <span m="1332310">you</span> <span m="1332450">proofs</span> <span m="1332720">by</span> <span m="1332840">picture</span> <span m="1333220">are</span> <span m="1333320">generally</span> <span m="1333850">not</span> <span m="1334440">a</span> <span m="1334540">good</span> <span m="1334720">thing.</span> <span m="1335530">Because</span> <span m="1335710">your</span> <span m="1335900">brain</span> <span m="1336200">just</span> <span m="1336400">locks</span> <span m="1336730">in--</span> <span m="1336870">oh,</span> <span m="1336970">that's</span> <span m="1337210">what</span> <span m="1337340">it has</span> <span m="1337530">to</span> <span m="1337620">look</span> <span m="1337810">like.</span> <span m="1339010">And</span> <span m="1339130">you</span> <span m="1339210">don't</span> <span m="1339570">think</span> <span m="1339750">about</span> <span m="1340070">other</span> <span m="1340290">ways</span> <span m="1340690">that it</span> <span m="1340870">might</span> <span m="1341420">look</span> <span m="1341610">like.</span> </p>
<p><span m="1342510">Now,</span> <span m="1342830">the</span> <span m="1342920">four</span> <span m="1343120">color</span> <span m="1343370">theorem</span> <span m="1343640">was</span> <span m="1343800">finally</span> <span m="1344240">proved</span> <span m="1345320">by</span> <span m="1345710">Appel</span> <span m="1346100">and</span> <span m="1346310">Haken</span> <span m="1347050">in</span> <span m="1347380">1977,</span> <span m="1349120">but</span> <span m="1349250">they</span> <span m="1349350">had</span> <span m="1349620">to</span> <span m="1349670">use</span> <span m="1349910">a</span> <span m="1349980">computer</span> <span m="1350930">to</span> <span m="1351080">check</span> <span m="1351510">thousands</span> <span m="1352230">of</span> <span m="1352340">cases.</span> <span m="1354970">Now,</span> <span m="1355330">this</span> <span m="1355570">was</span> <span m="1355710">a</span> <span m="1355770">little</span> <span m="1356170">disturbing</span> <span m="1356660">to</span> <span m="1356720">mathematicians,</span> <span m="1357510">because</span> <span m="1358870">how</span> <span m="1359070">do</span> <span m="1359140">they</span> <span m="1359270">know</span> <span m="1359480">the</span> <span m="1359590">computer</span> <span m="1360110">did</span> <span m="1360290">the</span> <span m="1360380">right</span> <span m="1360610">thing?</span> <span m="1363390">Your</span> <span m="1363530">colleague</span> <span m="1363910">writes</span> <span m="1364080">a</span> <span m="1364180">proof</span> <span m="1364390">on</span> <span m="1364460">the</span> <span m="1364530">board.</span> <span m="1364780">You</span> <span m="1364860">can</span> <span m="1364980">check</span> <span m="1365270">it.</span> <span m="1365630">But</span> <span m="1365760">how</span> <span m="1366030">do you know</span> <span m="1366200">the computer</span> <span m="1366570">didn't</span> <span m="1366790">mess</span> <span m="1367070">up,</span> <span m="1367300">or</span> <span m="1367380">not</span> <span m="1367590">do</span> <span m="1367700">some</span> <span m="1367850">cases?</span> </p>
<p><span m="1370130">Now,</span> <span m="1370680">everybody</span> <span m="1371020">believes</span> <span m="1371330">it's</span> <span m="1371450">true</span> <span m="1371650">now.</span> <span m="1372620">But</span> <span m="1372800">it's</span> <span m="1373310">unsatisfying.</span> </p>
<p><span m="1374780">A</span> <span m="1374890">few</span> <span m="1375050">years</span> <span m="1375360">ago,</span> <span m="1376270">a</span> <span m="1376370">12-page</span> <span m="1377290">human</span> <span m="1377580">proof</span> <span m="1378010">was</span> <span m="1378140">discovered,</span> <span m="1380420">but</span> <span m="1380530">it's</span> <span m="1380660">not</span> <span m="1380840">been</span> <span m="1380960">verified.</span> <span m="1381810">And</span> <span m="1382300">people</span> <span m="1382600">are</span> <span m="1382640">very</span> <span m="1382930">suspicious</span> <span m="1383450">of</span> <span m="1383600">it</span> <span m="1384180">because</span> <span m="1384520">the</span> <span m="1384630">proof</span> <span m="1384910">of</span> <span m="1384970">the</span> <span m="1385040">main</span> <span m="1385240">lemma</span> <span m="1386190">says,</span> <span m="1386800">quote,</span> <span m="1388020">"details</span> <span m="1388670">of</span> <span m="1388770">this</span> <span m="1389010">lemma</span> <span m="1389560">is</span> <span m="1389780">left</span> <span m="1390130">to</span> <span m="1390190">the</span> <span m="1390320">reader.</span> <span m="1390740">See</span> <span m="1391030">figure</span> <span m="1391360">seven."</span> <span m="1392540">That's</span> <span m="1392740">what</span> <span m="1392850">the</span> <span m="1392920">main lemma</span> <span m="1393290">of</span> <span m="1393350">the</span> <span m="1393430">proof</span> <span m="1393690">is.</span> <span m="1394300">But</span> <span m="1394400">people</span> <span m="1394660">think</span> <span m="1394980">that</span> <span m="1395190">maybe</span> <span m="1395380">there were</span> <span m="1395460">some</span> <span m="1395580">good</span> <span m="1395760">ideas</span> <span m="1396120">there,</span> <span m="1396270">but</span> <span m="1396450">very</span> <span m="1396990">suspicious</span> <span m="1397540">proof.</span> </p>
<p><span m="1399240">All</span> <span m="1399330">right,</span> <span m="1401170">let's</span> <span m="1401470">do</span> <span m="1401690">another</span> <span m="1402050">one,</span> <span m="1402770">another</span> <span m="1403000">proposition--</span> <span m="1404430">also</span> <span m="1404820">very</span> <span m="1405080">famous.</span> <span m="1407800">Every</span> <span m="1408290">even</span> <span m="1408520">integer</span> <span m="1412800">but</span> <span m="1413040">2--</span> <span m="1415150">actually,</span> <span m="1415490">positive</span> <span m="1416000">integer</span> <span m="1416220">but</span> <span m="1416300">2--</span> <span m="1417480">is</span> <span m="1417950">the</span> <span m="1418090">sum</span> <span m="1420920">of</span> <span m="1421350">two</span> <span m="1421560">primes.</span> <span m="1425560">For</span> <span m="1425770">example,</span> <span m="1428960">24</span> <span m="1430190">is</span> <span m="1430360">the</span> <span m="1430460">sum</span> <span m="1430710">of</span> <span m="1430790">11</span> <span m="1431170">and</span> <span m="1431280">13,</span> <span m="1432360">which</span> <span m="1432570">are</span> <span m="1432660">prime.</span> <span m="1437090">Anybody</span> <span m="1437400">know?</span> <span m="1437640">Is</span> <span m="1437720">this</span> <span m="1437860">true</span> <span m="1438110">or</span> <span m="1438210">false,</span> <span m="1440160">this</span> <span m="1440190">proposition?</span> <span m="1444070">Yeah?</span> </p>
<p><span m="1444370">AUDIENCE: I wish</span> <span m="1444670">I knew.</span> </p>
<p><span m="1445156">PROFESSOR: [LAUGHS]</span> <span m="1445642">Yeah,</span> <span m="1446130">that's</span> <span m="1446440">right.</span> <span m="1446710">Me</span> <span m="1446910">too.</span> <span m="1448120">Nobody</span> <span m="1448190">knows</span> <span m="1449520">if</span> <span m="1449650">this</span> <span m="1449830">is</span> <span m="1449940">true</span> <span m="1450110">or</span> <span m="1450200">false.</span> <span m="1451140">This</span> <span m="1451340">is</span> <span m="1451450">called</span> <span m="1452090">Goldbach's</span> <span m="1452700">conjecture.</span> <span m="1454326">It</span> <span m="1454800">was</span> <span m="1455210">conjectured</span> <span m="1455720">by</span> <span m="1456210">Christian</span> <span m="1456620">Goldbach</span> <span m="1457180">in</span> <span m="1457280">1742.</span> </p>
<p><span m="1459510">This</span> <span m="1459690">is</span> <span m="1459800">a</span> <span m="1459950">really</span> <span m="1460450">simple</span> <span m="1460840">proposition.</span> <span m="1462570">And</span> <span m="1463650">it's</span> <span m="1463830">amazing</span> <span m="1464290">it's</span> <span m="1464460">not</span> <span m="1464670">known.</span> <span m="1464850">In fact,</span> <span m="1465110">I</span> <span m="1465220">spent</span> <span m="1466710">a</span> <span m="1466880">couple</span> <span m="1467170">years</span> <span m="1467760">working</span> <span m="1468210">on--</span> <span m="1468450">I</span> <span m="1468560">thought,</span> <span m="1468730">oh, well,</span> <span m="1468970">this</span> <span m="1469120">has</span> <span m="1469290">to</span> <span m="1469350">be</span> <span m="1469450">easy</span> <span m="1469760">enough to</span> <span m="1469840">prove</span> <span m="1470100">when</span> <span m="1470210">I</span> <span m="1470270">was</span> <span m="1470780">younger,</span> <span m="1471850">and</span> <span m="1472840">didn't</span> <span m="1473020">get</span> <span m="1473150">very</span> <span m="1473330">far.</span> <span m="1474550">So</span> <span m="1474710">people</span> <span m="1475010">still</span> <span m="1475240">don't</span> <span m="1475440">know</span> <span m="1475910">if</span> <span m="1476090">it's</span> <span m="1476220">true.</span> </p>
<p><span m="1477010">And</span> <span m="1477190">in</span> <span m="1477260">fact,</span> <span m="1477810">it</span> <span m="1477970">was</span> <span m="1478170">listed</span> <span m="1478540">by</span> <span m="1478660">the</span> <span m="1478780"><i>Globe</i></span> <span m="1480270">as</span> <span m="1480710">one</span> <span m="1480840">of</span> <span m="1480880">the</span> <span m="1480960">great</span> <span m="1481240">unsolved</span> <span m="1481690">mysteries.</span> <span m="1482360">So</span> <span m="1482560">if</span> <span m="1482620">you</span> <span m="1482710">get</span> <span m="1482830">out</span> <span m="1482960">this</span> <span m="1483120"><i>Globe</i></span> <span m="1483430">article</span> <span m="1483810">here,</span> <span m="1485100">one of</span> <span m="1485230">the hand--</span> <span m="1485310">does</span> <span m="1485660">everybody</span> <span m="1485840">have</span> <span m="1486050">this</span> <span m="1486230">handout?</span> <span m="1488440">You</span> <span m="1488540">don't?</span> <span m="1488800">We'll get</span> <span m="1488900">it</span> <span m="1489010">passed</span> <span m="1489080">out.</span> <span m="1489420">Somebody</span> <span m="1489710">missing</span> <span m="1490000">that</span> <span m="1490150">handout</span> <span m="1490710">up</span> <span m="1490860">over</span> <span m="1491010">there</span> <span m="1491310">and</span> <span m="1491380">over</span> <span m="1491540">here?</span> <span m="1493150">All right,</span> <span m="1493340">if we get</span> <span m="1493600">those</span> <span m="1493810">passed</span> <span m="1494160">out.</span> </p>
<p><span m="1497080">Now,</span> <span m="1497240">it</span> <span m="1497340">lists</span> <span m="1497550">the</span> <span m="1497650">three</span> <span m="1497830">conjectures.</span> <span m="1499260">Do</span> <span m="1499350">you</span> <span m="1499430">see</span> <span m="1499980">Goldbach's</span> <span m="1500440">conjecture</span> <span m="1500850">there?</span> <span m="1503610">Now,</span> <span m="1503790">can</span> <span m="1503920">anybody</span> <span m="1505320">point</span> <span m="1505590">out</span> <span m="1505900">something</span> <span m="1506240">that's</span> <span m="1506430">a</span> <span m="1506480">little</span> <span m="1506720">disturbing</span> <span m="1507260">about</span> <span m="1508920">what</span> <span m="1509080">the</span> <span m="1509150"><i>Globe</i></span> <span m="1509480">says</span> <span m="1509810">about</span> <span m="1510020">Goldbach's</span> <span m="1510310">conjecture?</span> </p>
<p><span m="1513500">AUDIENCE: 9 as</span> <span m="1513992">a prime</span> <span m="1514484">number.</span> </p>
<p><span m="1514980">PROFESSOR: Yeah,</span> <span m="1515780">it</span> <span m="1515920">gives</span> <span m="1516110">the</span> <span m="1516260">example.</span> <span m="1517100">Like,</span> <span m="1517340">instead</span> <span m="1517560">of</span> <span m="1517640">24</span> <span m="1518190">is</span> <span m="1518270">11</span> <span m="1518520">plus</span> <span m="1518740">13,</span> <span m="1519120">it</span> <span m="1519220">says</span> <span m="1519470">20</span> <span m="1521010">is</span> <span m="1521190">the</span> <span m="1521280">sum</span> <span m="1521490">of</span> <span m="1521580">9</span> <span m="1522063">and</span> <span m="1522546">11.</span> <span m="1524410">Now,</span> <span m="1525590">if</span> <span m="1525730">we're</span> <span m="1525830">allowed</span> <span m="1526150">to</span> <span m="1526190">use</span> <span m="1526430">things</span> <span m="1526650">like</span> <span m="1526860">9</span> <span m="1527160">as</span> <span m="1527290">primes,</span> <span m="1527860">Goldbach's</span> <span m="1528240">conjecture's</span> <span m="1528690">pretty</span> <span m="1528930">easy</span> <span m="1529110">to</span> <span m="1529180">prove</span> <span m="1529560">is</span> <span m="1529650">true.</span> </p>
<p><span m="1533540">This</span> <span m="1533750">won't</span> <span m="1533910">be</span> <span m="1534010">the</span> <span m="1534110">last</span> <span m="1534400">time</span> <span m="1534610">we</span> <span m="1535270">get</span> <span m="1535410">examples</span> <span m="1535930">from</span> <span m="1535990">the</span> <span m="1536050">literature.</span> <span m="1536350">In fact,</span> <span m="1536510">we're</span> <span m="1536590">going</span> <span m="1536690">to</span> <span m="1536730">do this</span> <span m="1536880">a</span> <span m="1536940">lot,</span> <span m="1537970">along</span> <span m="1538290">this</span> <span m="1538410">theme</span> <span m="1538730">of,</span> <span m="1538860">you</span> <span m="1539000">cannot</span> <span m="1539450">believe</span> <span m="1540080">everything</span> <span m="1540420">you</span> <span m="1540560">read.</span> <span m="1541550">Now,</span> <span m="1541870">the</span> <span m="1541950"><i>Globe</i></span> <span m="1542230">is</span> <span m="1542320">easy</span> <span m="1542570">pickings,</span> <span m="1542960">but</span> <span m="1543060">we'll</span> <span m="1543130">do</span> <span m="1543250">some</span> <span m="1543380">more</span> <span m="1543520">interesting</span> <span m="1543800">ones</span> <span m="1543980">later.</span> </p>
<p><span m="1545370">Now,</span> <span m="1545520">this</span> <span m="1545710">article</span> <span m="1546080">lists</span> <span m="1546430">two</span> <span m="1546580">other</span> <span m="1546760">famous</span> <span m="1547130">conjectures</span> <span m="1547850">which</span> <span m="1548070">most</span> <span m="1548340">people</span> <span m="1548590">believe</span> <span m="1549020">to</span> <span m="1549100">be</span> <span m="1549210">true--</span> <span m="1551570">the</span> <span m="1552240">Riemann</span> <span m="1552700">hypothesis</span> <span m="1555440">after</span> <span m="1555850">an</span> <span m="1556270">1859</span> <span m="1557110">paper</span> <span m="1557450">written</span> <span m="1557730">by</span> <span m="1557930">Bernard</span> <span m="1559240">Riemann</span> <span m="1560280">suggested</span> <span m="1560580">that</span> <span m="1560880">zeros</span> <span m="1561260">in</span> <span m="1561320">an</span> <span m="1561470">infinite</span> <span m="1561870">series</span> <span m="1562260">of</span> <span m="1562340">numbers</span> <span m="1562740">known as</span> <span m="1562880">a</span> <span m="1563060">zeta</span> <span m="1563260">function</span> <span m="1563690">form</span> <span m="1564350">along</span> <span m="1564610">a</span> <span m="1564660">straight</span> <span m="1564970">line</span> <span m="1565170">on that</span> <span m="1565250">complex</span> <span m="1565690">plane.</span> <span m="1566690">The</span> <span m="1566780">hypothesis</span> <span m="1567430">has</span> <span m="1567570">been</span> <span m="1568030">proved</span> <span m="1568075">to</span> <span m="1568120">1.5</span> <span m="1568980">billion</span> <span m="1569460">zeros,</span> <span m="1570800">not</span> <span m="1571130">far</span> <span m="1571350">enough</span> <span m="1571510">to</span> <span m="1571670">prove</span> <span m="1571890">it</span> <span m="1571950">completely.</span> <span m="1573860">If</span> <span m="1574020">they</span> <span m="1574130">did</span> <span m="1574280">1.5</span> <span m="1574820">trillion</span> <span m="1575250">zeros,</span> <span m="1575610">it</span> <span m="1575660">wouldn't</span> <span m="1575880">be</span> <span m="1575990">far</span> <span m="1576360">enough</span> <span m="1576540">to</span> <span m="1576640">prove</span> <span m="1576830">it</span> <span m="1576900">completely,</span> <span m="1577340">of</span> <span m="1577430">course.</span> </p>
<p><span m="1579230">And</span> <span m="1579380">then</span> <span m="1581940">the--</span> <span m="1583070">no,</span> <span m="1583250">actually, the</span> <span m="1583570">Riemann</span> <span m="1583820">hypothesis,</span> <span m="1584510">a</span> <span m="1584580">couple</span> <span m="1584850">years</span> <span m="1585090">ago,</span> <span m="1585920">somebody</span> <span m="1586200">credible</span> <span m="1586920">claimed</span> <span m="1587200">to have</span> <span m="1587320">proved</span> <span m="1587620">it.</span> <span m="1588150">Proof</span> <span m="1588370">turned</span> <span m="1588610">out</span> <span m="1588850">not</span> <span m="1589000">to</span> <span m="1589090">be</span> <span m="1589180">right.</span> <span m="1590320">Then</span> <span m="1590490">there's</span> <span m="1590710">the</span> <span m="1590810">Poincare</span> <span m="1591470">conjecture.</span> <span m="1592910">Now,</span> <span m="1593110">this</span> <span m="1593450">one</span> <span m="1593680">was</span> <span m="1594600">finished</span> <span m="1595020">off.</span> <span m="1595570">It</span> <span m="1595660">was</span> <span m="1595830">proved</span> <span m="1596160">to</span> <span m="1596200">be</span> <span m="1596310">true</span> <span m="1596620">in</span> <span m="1596700">2003</span> <span m="1598050">by</span> <span m="1598290">a</span> <span m="1598400">Russian</span> <span m="1598810">named</span> <span m="1599090">Grigori</span> <span m="1599350">Perelman.</span> </p>
<p><span m="1601250">The</span> <span m="1601340">conjecture</span> <span m="1601980">says,</span> <span m="1602720">roughly</span> <span m="1603050">speaking,</span> <span m="1603560">that</span> <span m="1604130">3D</span> <span m="1604760">objects</span> <span m="1605470">without</span> <span m="1605850">holes,</span> <span m="1606420">like</span> <span m="1606790">no a</span> <span m="1606880">doughnut,</span> <span m="1608180">are</span> <span m="1608420">equivalent</span> <span m="1609420">to</span> <span m="1609560">the</span> <span m="1609790">sphere.</span> <span m="1610200">They</span> <span m="1610290">can</span> <span m="1610420">sort</span> <span m="1610590">of</span> <span m="1610640">be</span> <span m="1610790">deformed</span> <span m="1611450">into</span> <span m="1611780">a</span> <span m="1612050">sphere.</span> <span m="1613350">This</span> <span m="1613560">is</span> <span m="1613710">known</span> <span m="1614090">to</span> <span m="1614140">be</span> <span m="1614250">true</span> <span m="1614500">in</span> <span m="1614590">four</span> <span m="1614800">dimensions</span> <span m="1615220">and</span> <span m="1615310">higher,</span> <span m="1615700">but</span> <span m="1615840">nobody</span> <span m="1616170">could</span> <span m="1616310">prove</span> <span m="1616510">it</span> <span m="1616610">for</span> <span m="1616700">three</span> <span m="1616890">dimensions</span> <span m="1617370">until</span> <span m="1617590">Perelman</span> <span m="1617980">came</span> <span m="1618190">along.</span> </p>
<p><span m="1619490">Now,</span> <span m="1619610">there's</span> <span m="1619790">a</span> <span m="1619850">bit</span> <span m="1620000">of</span> <span m="1620070">a</span> <span m="1620130">controversy</span> <span m="1620980">around</span> <span m="1621280">this</span> <span m="1621490">guy.</span> <span m="1622880">He</span> <span m="1623070">had</span> <span m="1623150">an</span> <span m="1623230">80-page</span> <span m="1623780">proof,</span> <span m="1624150">but</span> <span m="1624310">didn't</span> <span m="1624490">have</span> <span m="1624640">all</span> <span m="1624760">the</span> <span m="1624860">details.</span> <span m="1626290">So</span> <span m="1626340">then</span> <span m="1626470">other</span> <span m="1626760">teams</span> <span m="1627130">of</span> <span m="1627190">mathematicians</span> <span m="1627880">got</span> <span m="1628060">together</span> <span m="1628570">and</span> <span m="1629220">wrote</span> <span m="1629530">350</span> <span m="1630310">pages</span> <span m="1630860">of</span> <span m="1631000">details.</span> <span m="1632770">And</span> <span m="1632910">then</span> <span m="1633040">most</span> <span m="1633270">people</span> <span m="1633440">believe</span> <span m="1633810">now</span> <span m="1634200">that</span> <span m="1634470">it's</span> <span m="1634640">right,</span> <span m="1635080">and</span> <span m="1635270">that</span> <span m="1635370">his</span> <span m="1635500">original</span> <span m="1636020">proof</span> <span m="1636790">might not</span> <span m="1636940">have</span> <span m="1637110">had</span> <span m="1637260">all</span> <span m="1637350">the</span> <span m="1637430">details,</span> <span m="1637880">but</span> <span m="1637990">he</span> <span m="1638150">had</span> <span m="1638320">the</span> <span m="1638420">right</span> <span m="1639040">structure</span> <span m="1639420">of the</span> <span m="1639530">proof.</span> </p>
<p><span m="1640540">So</span> <span m="1641380">he</span> <span m="1641610">won</span> <span m="1641930">prizes</span> <span m="1642430">for</span> <span m="1642510">this.</span> <span m="1643040">He</span> <span m="1643200">won</span> <span m="1643340">the</span> <span m="1643420">highest</span> <span m="1643810">prize</span> <span m="1644080">in</span> <span m="1644140">mathematics,</span> <span m="1644720">the</span> <span m="1644800">Fields</span> <span m="1645130">Medal.</span> <span m="1646090">And</span> <span m="1646800">just</span> <span m="1647120">earlier</span> <span m="1647400">this</span> <span m="1647560">year,</span> <span m="1648280">he</span> <span m="1648400">was</span> <span m="1648550">awarded</span> <span m="1648980">the</span> <span m="1649070">$1</span> <span m="1649360">million</span> <span m="1649660">Millennium</span> <span m="1650400">Prize.</span> </p>
<p><span m="1651450">And</span> <span m="1651600">there's</span> <span m="1651770">about</span> <span m="1652090">six</span> <span m="1652410">problems</span> <span m="1652830">or</span> <span m="1652930">so</span> <span m="1653250">that</span> <span m="1653360">if</span> <span m="1653460">you</span> <span m="1653560">solve</span> <span m="1653930">one</span> <span m="1654090">of</span> <span m="1654160">them,</span> <span m="1654790">the</span> <span m="1654880">Clay Institute</span> <span m="1655460">gives</span> <span m="1655650">you</span> <span m="1655750">a</span> <span m="1655780">million</span> <span m="1656150">dollars.</span> <span m="1656690">And</span> <span m="1656800">he's</span> <span m="1656930">the</span> <span m="1657010">first</span> <span m="1657360">one</span> <span m="1657600">to</span> <span m="1658150">win</span> <span m="1658350">the</span> <span m="1658420">million</span> <span m="1658700">dollars.</span> <span m="1660100">Now, the</span> <span m="1660190">guy's</span> <span m="1660420">a</span> <span m="1660470">little</span> <span m="1660640">strange.</span> <span m="1661440">He</span> <span m="1661980">rejected</span> <span m="1662500">the</span> <span m="1662580">Fields</span> <span m="1662930">Medal</span> <span m="1663280">and</span> <span m="1663350">refused</span> <span m="1663820">to</span> <span m="1663900">go</span> <span m="1664140">to</span> <span m="1664190">the</span> <span m="1664290">ceremony</span> <span m="1664820">where</span> <span m="1665140">he</span> <span m="1665300">was</span> <span m="1665470">being</span> <span m="1665680">honored.</span> <span m="1666350">And</span> <span m="1666510">he's</span> <span m="1666730">recently</span> <span m="1667180">rejected</span> <span m="1667700">the</span> <span m="1667760">Millennium</span> <span m="1668180">prize.</span> </p>
<p><span m="1670960">And</span> <span m="1671100">anyway,</span> <span m="1672050">this</span> <span m="1672250">area's</span> <span m="1672560">murky,</span> <span m="1673140">and</span> <span m="1673220">we</span> <span m="1673310">have</span> <span m="1673510">an</span> <span m="1673600">expert</span> <span m="1674970">to</span> <span m="1675430">explain</span> <span m="1675850">it</span> <span m="1675910">all</span> <span m="1676080">for</span> <span m="1676380">us</span> <span m="1676510">on</span> <span m="1676650">video,</span> <span m="1677060">which</span> <span m="1677210">I</span> <span m="1677260">thought</span> <span m="1677450">I'd</span> <span m="1677580">show.</span> </p>
<p><span m="1686360">All</span> <span m="1686490">right,</span> <span m="1686950">let's</span> <span m="1687200">do</span> <span m="1688370">a</span> <span m="1688440">simpler</span> <span m="1688830">one</span> <span m="1689170">here.</span> <span m="1693510">For</span> <span m="1693730">all</span> <span m="1693990">n</span> <span m="1694790">in</span> <span m="1694990">Z,</span> <span m="1697240">n</span> <span m="1697580">greater</span> <span m="1697820">than or</span> <span m="1697880">equal</span> <span m="1698130">to</span> <span m="1698230">2</span> <span m="1699620">implies</span> <span m="1700780">n</span> <span m="1701100">squared</span> <span m="1701940">is</span> <span m="1702200">greater</span> <span m="1702490">than</span> <span m="1702590">or</span> <span m="1702690">equal</span> <span m="1702800">to</span> <span m="1702880">4.</span> <span m="1704240">Now,</span> <span m="1704420">Z,</span> <span m="1704910">we</span> <span m="1705060">use</span> <span m="1705440">for</span> <span m="1705540">the</span> <span m="1705730">integers.</span> <span m="1710230">And</span> <span m="1710600">so</span> <span m="1710750">that</span> <span m="1710950">would</span> <span m="1711060">be</span> <span m="1711980">0,</span> <span m="1712380">1,</span> <span m="1712770">minus</span> <span m="1713190">1,</span> <span m="1713610">2,</span> <span m="1714120">minus</span> <span m="1714490">2,</span> <span m="1715400">and</span> <span m="1715660">so</span> <span m="1715850">forth.</span> </p>
<p><span m="1717440">And</span> <span m="1717650">this</span> <span m="1717860">symbol</span> <span m="1718190">here</span> <span m="1719590">is</span> <span m="1720180">implies.</span> <span m="1725310">I</span> <span m="1725670">In</span> <span m="1725780">fact,</span> <span m="1726340">one thing</span> <span m="1726520">you</span> <span m="1726620">can</span> <span m="1726800">notice</span> <span m="1727100">when</span> <span m="1727180">you</span> <span m="1727290">read</span> <span m="1727500">the</span> <span m="1727590">text</span> <span m="1728690">is</span> <span m="1728880">we</span> <span m="1729010">use</span> <span m="1729400">different</span> <span m="1729770">notation</span> <span m="1731030">there</span> <span m="1731670">as</span> <span m="1731820">the</span> <span m="1731920">standard</span> <span m="1732330">than</span> <span m="1732440">I</span> <span m="1732530">will</span> <span m="1732660">use</span> <span m="1732970">in</span> <span m="1733040">lecture.</span> <span m="1733960">And</span> <span m="1734140">there's</span> <span m="1734310">lots</span> <span m="1734720">of</span> <span m="1734970">ways</span> <span m="1735490">of</span> <span m="1735580">doing</span> <span m="1735860">it.</span> <span m="1736060">You</span> <span m="1736160">could</span> <span m="1736260">have</span> <span m="1736290">a</span> <span m="1736360">double</span> <span m="1736810">arrow,</span> <span m="1737230">a</span> <span m="1737280">single</span> <span m="1737740">arrow.</span> <span m="1738300">You</span> <span m="1738440">could</span> <span m="1738550">write</span> <span m="1738800">out</span> <span m="1738930">implies</span> <span m="1739460">every</span> <span m="1739650">time</span> <span m="1740000">as it's</span> <span m="1740180">done</span> <span m="1740330">in</span> <span m="1740370">the</span> <span m="1740470">text.</span> <span m="1741200">And it</span> <span m="1741400">doesn't</span> <span m="1741630">really</span> <span m="1741880">matter</span> <span m="1742170">which</span> <span m="1742360">one</span> <span m="1742520">you</span> <span m="1742620">want</span> <span m="1742800">to</span> <span m="1742850">use</span> <span m="1743730">as</span> <span m="1744000">long as</span> <span m="1744220">you use</span> <span m="1744430">one</span> <span m="1744700">of</span> <span m="1744760">the</span> <span m="1744860">conventions</span> <span m="1745420">for</span> <span m="1745620">implies.</span> </p>
<p><span m="1747630">And</span> <span m="1747770">let</span> <span m="1747840">me</span> <span m="1747930">define</span> <span m="1748430">what</span> <span m="1749660">implies</span> <span m="1750180">means.</span> <span m="1766910">An</span> <span m="1767160">implication</span> <span m="1773650">p</span> <span m="1774700">implies</span> <span m="1775190">q</span> <span m="1777230">is</span> <span m="1777920">said</span> <span m="1778060">to</span> <span m="1778110">be</span> <span m="1778230">true</span> <span m="1780340">if</span> <span m="1781300">p</span> <span m="1782040">is</span> <span m="1782260">false</span> <span m="1783830">or</span> <span m="1784580">q</span> <span m="1785530">is</span> <span m="1785700">true,</span> <span m="1787370">either</span> <span m="1787580">one.</span> <span m="1788440">So</span> <span m="1788710">we</span> <span m="1788850">can</span> <span m="1789360">write</span> <span m="1789590">this</span> <span m="1789750">down</span> <span m="1790070">in</span> <span m="1790130">terms</span> <span m="1790360">of</span> <span m="1790420">a</span> <span m="1790480">truth</span> <span m="1790730">table</span> <span m="1795480">as</span> <span m="1795680">follows.</span> <span m="1796800">You</span> <span m="1797240">have the</span> <span m="1797360">values</span> <span m="1797680">of</span> <span m="1797780">p</span> <span m="1798020">and</span> <span m="1798140">q.</span> <span m="1799680">And</span> <span m="1799820">I'll</span> <span m="1799870">give</span> <span m="1800030">the</span> <span m="1800100">value</span> <span m="1800430">of</span> <span m="1800500">p</span> <span m="1800710">implies</span> <span m="1801160">q.</span> </p>
<p><span m="1803048">If</span> <span m="1803520">p</span> <span m="1805860">is</span> <span m="1805970">true</span> <span m="1806220">and</span> <span m="1806320">q</span> <span m="1806510">is</span> <span m="1806630">true,</span> <span m="1807820">what</span> <span m="1807950">about</span> <span m="1808160">p</span> <span m="1808290">implies</span> <span m="1808650">q?</span> <span m="1811575">It's</span> <span m="1812060">true,</span> <span m="1812790">because</span> <span m="1813210">q</span> <span m="1813510">is</span> <span m="1813600">true in</span> <span m="1814055">the</span> <span m="1814510">definition.</span> <span m="1816330">If</span> <span m="1816600">p</span> <span m="1816940">is</span> <span m="1817070">true</span> <span m="1817380">and</span> <span m="1817480">q</span> <span m="1817670">is</span> <span m="1817800">false?</span> </p>
<p><span m="1819821">AUDIENCE: False.</span> </p>
<p><span m="1820260">PROFESSOR: False.</span> <span m="1822910">P</span> <span m="1823170">is</span> <span m="1823340">false.</span> <span m="1823880">Q</span> <span m="1824120">is</span> <span m="1824240">true.</span> <span m="1827292">True.</span> <span m="1828190">What</span> <span m="1828400">about</span> <span m="1828710">false</span> <span m="1829870">and</span> <span m="1830070">false?</span> <span m="1832440">It's</span> <span m="1832630">true.</span> <span m="1834230">Even</span> <span m="1834490">though</span> <span m="1834960">this</span> <span m="1835190">is</span> <span m="1835310">false,</span> <span m="1835670">as</span> <span m="1835790">long</span> <span m="1835980">as</span> <span m="1836100">p</span> <span m="1836270">is</span> <span m="1836420">false,</span> <span m="1836760">p</span> <span m="1836900">implies</span> <span m="1837250">q</span> <span m="1837450">is</span> <span m="1838120">true.</span> <span m="1840790">So</span> <span m="1841660">this</span> <span m="1841880">is</span> <span m="1841960">important</span> <span m="1842360">to</span> <span m="1842400">remember.</span> <span m="1843520">False</span> <span m="1844120">implies</span> <span m="1844800">anything</span> <span m="1846600">is</span> <span m="1846810">true,</span> <span m="1848480">which</span> <span m="1848520">is</span> <span m="1848620">a</span> <span m="1848670">little</span> <span m="1849480">strange.</span> </p>
<p><span m="1849800">There's</span> <span m="1849900">a</span> <span m="1849960">famous</span> <span m="1850330">expression.</span> <span m="1851880">If</span> <span m="1852120">pigs</span> <span m="1852440">could</span> <span m="1852570">fly,</span> <span m="1853070">I</span> <span m="1853210">would</span> <span m="1853360">be</span> <span m="1853480">king.</span> <span m="1855950">Is</span> <span m="1856060">that</span> <span m="1856210">true?</span> <span m="1859920">Sort</span> <span m="1860400">of.</span> <span m="1861020">In</span> <span m="1861150">fact,</span> <span m="1861960">this</span> <span m="1862230">statement,</span> <span m="1864650">pigs</span> <span m="1865140">fly</span> <span m="1867740">implies</span> <span m="1869640">I'm</span> <span m="1869970">king--</span> <span m="1873440">that's</span> <span m="1873690">true,</span> <span m="1876340">because</span> <span m="1876640">pigs</span> <span m="1876890">don't</span> <span m="1877070">fly.</span> <span m="1878400">Doesn't</span> <span m="1878660">matter</span> <span m="1879010">whether</span> <span m="1879230">or</span> <span m="1879260">not</span> <span m="1879450">I'm</span> <span m="1879600">king,</span> <span m="1880250">which</span> <span m="1880440">I'm</span> <span m="1880560">not.</span> <span m="1881420">Since</span> <span m="1881620">pigs</span> <span m="1881860">don't</span> <span m="1882080">fly,</span> <span m="1883060">even</span> <span m="1883240">though</span> <span m="1883330">that's</span> <span m="1883570">false,</span> <span m="1884010">the</span> <span m="1884840">implication</span> <span m="1885600">is</span> <span m="1885810">true.</span> </p>
<p><span m="1887500">Now,</span> <span m="1887590">some</span> <span m="1887780">of</span> <span m="1887850">you have</span> <span m="1888050">worked</span> <span m="1888540">on</span> <span m="1888690">these</span> <span m="1888860">things</span> <span m="1889030">before.</span> <span m="1889580">It's</span> <span m="1889940">second</span> <span m="1890190">nature.</span> <span m="1890470">If</span> <span m="1890550">you</span> <span m="1890620">haven't,</span> <span m="1891560">you</span> <span m="1891850">want</span> <span m="1891950">to</span> <span m="1891990">start</span> <span m="1892190">getting</span> <span m="1892390">familiar</span> <span m="1893760">with</span> <span m="1893880">that.</span> <span m="1896780">Let's</span> <span m="1896920">do</span> <span m="1896990">another</span> <span m="1897210">example.</span> </p>
<p><span m="1909700">What</span> <span m="1909850">about</span> <span m="1910090">this</span> <span m="1910440">proposition?</span> <span m="1913850">For</span> <span m="1914030">all</span> <span m="1914190">integers,</span> <span m="1914680">n</span> <span m="1914840">in</span> <span m="1914930">Z,</span> <span m="1916580">n</span> <span m="1917320">greater than</span> <span m="1917540">or</span> <span m="1917630">equal</span> <span m="1917840">to</span> <span m="1917940">2--</span> <span m="1920610">this</span> <span m="1920830">is</span> <span m="1921100">if</span> <span m="1921270">and</span> <span m="1921360">only</span> <span m="1921710">if--</span> <span m="1924200">n</span> <span m="1924410">squared</span> <span m="1925080">greater</span> <span m="1925320">than or</span> <span m="1925380">equal</span> <span m="1925580">to</span> <span m="1925670">4.</span> <span m="1927890">Is</span> <span m="1927970">that</span> <span m="1928120">true?</span> <span m="1932830">Is</span> <span m="1933150">n</span> <span m="1934420">only</span> <span m="1934580">bigger</span> <span m="1934860">than</span> <span m="1934980">2</span> <span m="1935190">if</span> <span m="1935340">and</span> <span m="1935410">only</span> <span m="1935600">if</span> <span m="1935730">n</span> <span m="1935860">squared</span> <span m="1936170">is bigger</span> <span m="1936330">than</span> <span m="1936410">4?</span> </p>
<p><span m="1938030">It's</span> <span m="1938440">false.</span> <span m="1939100">What's</span> <span m="1939330">an</span> <span m="1939390">example</span> <span m="1939840">of n</span> <span m="1940170">for which</span> <span m="1940400">that's</span> <span m="1940630">false?</span> <span m="1942490">Negative,</span> <span m="1943110">all</span> <span m="1943320">right?</span> <span m="1943620">So</span> <span m="1944010">it's</span> <span m="1944160">false.</span> <span m="1945980">n</span> <span m="1946240">equals</span> <span m="1946590">negative</span> <span m="1947010">3,</span> <span m="1948970">all</span> <span m="1949060">right?</span> <span m="1950560">Negative</span> <span m="1950920">3</span> <span m="1951060">squared</span> <span m="1951390">is</span> <span m="1951490">bigger</span> <span m="1951690">than</span> <span m="1951940">or</span> <span m="1951980">equal</span> <span m="1952180">to</span> <span m="1952260">4,</span> <span m="1952620">but</span> <span m="1952810">negative</span> <span m="1953130">3</span> <span m="1953270">is</span> <span m="1953390">not</span> <span m="1953670">bigger</span> <span m="1953890">than</span> <span m="1953960">or</span> <span m="1953980">equal</span> <span m="1954210">to 2.</span> </p>
<p><span m="1954500">And in</span> <span m="1954640">fact</span> <span m="1956170">this</span> <span m="1956370">if</span> <span m="1956530">and</span> <span m="1956620">only</span> <span m="1956880">if</span> <span m="1957010">means</span> <span m="1959530">you</span> <span m="1959670">have</span> <span m="1959970">to</span> <span m="1960070">have</span> <span m="1960270">an</span> <span m="1960320">implication</span> <span m="1960970">both</span> <span m="1961230">ways.</span> <span m="1963660">So</span> <span m="1963770">you</span> <span m="1963830">have</span> <span m="1963960">to</span> <span m="1964030">check</span> <span m="1964540">both</span> <span m="1964780">ways</span> <span m="1965100">for</span> <span m="1965350">it.</span> <span m="1965810">So</span> <span m="1965940">let's</span> <span m="1966100">do</span> <span m="1966190">the</span> <span m="1966300">truth</span> <span m="1966560">table--</span> <span m="1966850">extend</span> <span m="1967130">this</span> <span m="1967260">truth</span> <span m="1967470">table</span> <span m="1967810">out</span> <span m="1968000">here</span> <span m="1971470">to</span> <span m="1971590">do  the</span> <span m="1971700">truth</span> <span m="1971960">table</span> <span m="1972280">for</span> <span m="1972440">p</span> <span m="1974460">if</span> <span m="1974590">and</span> <span m="1974660">only</span> <span m="1974810">if</span> <span m="1974900">q.</span> </p>
<p><span m="1984740">So</span> <span m="1984850">here are</span> <span m="1985180">p</span> <span m="1985380">and</span> <span m="1985490">q.</span> <span m="1988590">Is</span> <span m="1988770">q</span> <span m="1988950">implies</span> <span m="1989370">p</span> <span m="1989870">true</span> <span m="1990480">for</span> <span m="1990590">this</span> <span m="1990770">row?</span> <span m="1992800">Does</span> <span m="1993540">true</span> <span m="1994010">imply</span> <span m="1994280">true?</span> <span m="1996760">Yeah.</span> <span m="1998000">False</span> <span m="1998410">implies</span> <span m="1998890">true?</span> <span m="2000891">That's</span> <span m="2001300">true.</span> <span m="2002120">True</span> <span m="2002400">does</span> <span m="2002560">not</span> <span m="2002800">apply</span> <span m="2003110">false.</span> <span m="2003570">That's</span> <span m="2003770">false.</span> <span m="2005160">And</span> <span m="2005310">false</span> <span m="2005600">implies</span> <span m="2005960">false.</span> </p>
<p><span m="2007660">And</span> <span m="2007810">so</span> <span m="2007900">now,</span> <span m="2008210">we</span> <span m="2008330">can</span> <span m="2008470">see</span> <span m="2009380">where</span> <span m="2009690">p</span> <span m="2010760">is</span> <span m="2010950">if</span> <span m="2011110">and</span> <span m="2011190">only</span> <span m="2011490">if</span> <span m="2011630">q.</span> <span m="2013500">If</span> <span m="2013680">they're</span> <span m="2013840">both</span> <span m="2015100">true,</span> <span m="2015700">then</span> <span m="2016050">it's</span> <span m="2016170">true</span> <span m="2016440">here.</span> <span m="2017860">What</span> <span m="2017990">about</span> <span m="2018200">here?</span> <span m="2018660">Is</span> <span m="2018900">p</span> <span m="2019190">true</span> <span m="2019440">if</span> <span m="2019550">and</span> <span m="2019610">only</span> <span m="2019780">if</span> <span m="2019870">q</span> <span m="2020080">is</span> <span m="2020180">true</span> <span m="2021020">in</span> <span m="2021130">this</span> <span m="2021280">case?</span> <span m="2024360">No,</span> <span m="2025460">because</span> <span m="2025720">p</span> <span m="2025910">implies</span> <span m="2026260">q</span> <span m="2026540">is</span> <span m="2026680">false,</span> <span m="2027750">but</span> <span m="2028010">q</span> <span m="2028190">implies</span> <span m="2028530">p</span> <span m="2028660">is</span> <span m="2028780">true.</span> <span m="2029190">So</span> <span m="2029260">it's</span> <span m="2029380">false.</span> <span m="2030980">False</span> <span m="2031370">here.</span> </p>
<p><span m="2034570">I</span> <span m="2034620">made</span> <span m="2034770">a</span> <span m="2034800">mistake</span> <span m="2035300">there,</span> <span m="2035830">right?</span> <span m="2036490">That</span> <span m="2036660">was</span> <span m="2036750">true--</span> <span m="2037650">oops.</span> <span m="2040070">And</span> <span m="2040210">true</span> <span m="2040680">if and</span> <span m="2040880">only if</span> <span m="2041100">true,</span> <span m="2041670">OK.</span> <span m="2041900">They're</span> <span m="2041990">both</span> <span m="2042230">true,</span> <span m="2042510">so</span> <span m="2043420">we're</span> <span m="2043580">OK.</span> </p>
<p><span m="2045240">So</span> <span m="2045440">p</span> <span m="2045770">if</span> <span m="2045870">and</span> <span m="2045940">only</span> <span m="2046150">if</span> <span m="2046270">q</span> <span m="2046540">is</span> <span m="2046650">true</span> <span m="2046990">when</span> <span m="2047120">they're</span> <span m="2047240">both</span> <span m="2047600">true</span> <span m="2048260">or</span> <span m="2048340">both</span> <span m="2048620">false.</span> <span m="2049499">And</span> <span m="2049840">that's</span> <span m="2050110">it.</span> <span m="2050744">If</span> <span m="2051100">they're</span> <span m="2051300">different,</span> <span m="2051739">then</span> <span m="2051900">it's</span> <span m="2052139">not</span> <span m="2052290">true.</span> <span m="2053889">The</span> <span m="2053989">key</span> <span m="2054260">here</span> <span m="2054600">is</span> <span m="2054750">to</span> <span m="2054850">always</span> <span m="2055389">check</span> <span m="2056010">both</span> <span m="2056449">ways.</span> <span m="2057860">So</span> <span m="2057989">if</span> <span m="2058060">you're</span> <span m="2058210">asked</span> <span m="2058480">to</span> <span m="2058560">prove</span> <span m="2058760">an</span> <span m="2058840">if and only</span> <span m="2059250">if,</span> <span m="2060139">you</span> <span m="2060239">have to</span> <span m="2060370">prove</span> <span m="2061100">that</span> <span m="2061239">way,</span> <span m="2062150">and</span> <span m="2062350">that</span> <span m="2062540">way.</span> </p>
<p><span m="2066679">We've</span> <span m="2066870">just</span> <span m="2067040">done</span> <span m="2067230">about</span> <span m="2067620">15</span> <span m="2068090">propositions.</span> <span m="2070239">Is</span> <span m="2070540">every</span> <span m="2070870">sentence</span> <span m="2071290">a</span> <span m="2071360">proposition?</span> <span m="2076219">Yes?</span> <span m="2076570">No?</span> </p>
<p><span m="2077434">AUDIENCE: No.</span> </p>
<p><span m="2077929">PROFESSOR: No.</span> <span m="2078219">What's</span> <span m="2078460">an</span> <span m="2078520">example</span> <span m="2078989">of something</span> <span m="2079270">that's no</span> <span m="2079440">a</span> <span m="2079489">proposition?</span> </p>
<p><span m="2081240">AUDIENCE: This</span> <span m="2081677">statement</span> <span m="2082114">is false.</span> </p>
<p><span m="2082989">PROFESSOR: A</span> <span m="2083090">what?</span> </p>
<p><span m="2083409">AUDIENCE: This</span> <span m="2083811">statement</span> <span m="2084213">is false.</span> </p>
<p><span m="2085420">PROFESSOR: This</span> <span m="2085730">statement</span> <span m="2086090">is</span> <span m="2086270">false.</span> <span m="2087719">That's</span> <span m="2087880">true.</span> <span m="2088590">Well,</span> <span m="2089300">it's</span> <span m="2089510">true</span> <span m="2089949">it's</span> <span m="2090320">not</span> <span m="2090520">a</span> <span m="2090760">proposition.</span> <span m="2092020">Because</span> <span m="2092300">if</span> <span m="2092400">it</span> <span m="2092520">were</span> <span m="2092639">true,</span> <span m="2093580">it</span> <span m="2093620">wouldn't</span> <span m="2093810">be</span> <span m="2093920">false.</span> <span m="2094360">And if</span> <span m="2094460">was</span> <span m="2094650">false,</span> <span m="2095000">then it'd</span> <span m="2095139">be</span> <span m="2095250">true</span> <span m="2095429">and you'd</span> <span m="2095610">have a</span> <span m="2095659">contradiction.</span> <span m="2096909">So</span> <span m="2097010">it's</span> <span m="2097139">neither</span> <span m="2097500">true</span> <span m="2097730">nor</span> <span m="2097960">false.</span> </p>
<p><span m="2098850">What's</span> <span m="2099010">a</span> <span m="2099070">more</span> <span m="2099230">simple</span> <span m="2099700">example</span> <span m="2100170">of</span> <span m="2100390">something</span> <span m="2100590">that's</span> <span m="2100730">not</span> <span m="2101000">a</span> <span m="2101060">proposition?</span> </p>
<p><span m="2101620">AUDIENCE: This is</span> <span m="2102103">a tissue.</span> <span m="2103069">Isn't</span> <span m="2103552">that</span> <span m="2104035">a</span> <span m="2104518">[INAUDIBLE]?</span> </p>
<p><span m="2105484">PROFESSOR: Ooh.</span> <span m="2106940">Boy,</span> <span m="2107230">I would have</span> <span m="2107610">said</span> <span m="2107935">that's</span> <span m="2108260">true</span> <span m="2108640">in</span> <span m="2109020">some</span> <span m="2110130">world.</span> <span m="2111470">Because</span> <span m="2111860">yeah,</span> <span m="2112070">that's</span> <span m="2112250">a</span> <span m="2112320">tissue.</span> <span m="2113420">So</span> <span m="2113560">it's</span> <span m="2113660">a</span> <span m="2113710">true</span> <span m="2113910">statement.</span> </p>
<p><span m="2116790">AUDIENCE: Hello.</span> </p>
<p><span m="2117670">PROFESSOR: Hello.</span> <span m="2118690">That's</span> <span m="2118990">good.</span> <span m="2119140">That's</span> <span m="2119320">neither</span> <span m="2119490">true</span> <span m="2119740">or</span> <span m="2119810">false,</span> <span m="2120950">yeah.</span> <span m="2121590">A</span> <span m="2121730">question.</span> <span m="2122720">Who are</span> <span m="2122940">you--</span> <span m="2124140">neither</span> <span m="2124340">true</span> <span m="2124580">nor</span> <span m="2124640">false.</span> <span m="2125080">So</span> <span m="2125180">not</span> <span m="2125360">everything</span> <span m="2126260">is</span> <span m="2126400">a</span> <span m="2126450">proposition.</span> <span m="2127000">But in</span> <span m="2127120">this</span> <span m="2127290">course,</span> <span m="2127570">pretty</span> <span m="2127740">much</span> <span m="2127930">everything</span> <span m="2128220">we</span> <span m="2128320">deal</span> <span m="2128570">with</span> <span m="2129360">will</span> <span m="2129540">be</span> <span m="2129660">a</span> <span m="2129710">proposition.</span> </p>
<p><span m="2131620">All</span> <span m="2131780">right,</span> <span m="2132030">so</span> <span m="2133150">that's</span> <span m="2133400">it</span> <span m="2133500">for</span> <span m="2133600">propositions.</span> <span m="2134280">Any</span> <span m="2134430">questions</span> <span m="2134930">on</span> <span m="2135030">propositions?</span> </p>
<p><span m="2138460">Next,</span> <span m="2138830">we're</span> <span m="2138900">going</span> <span m="2138980">to</span> <span m="2139020">talk</span> <span m="2139280">about</span> <span m="2140850">axioms.</span> <span m="2147540">Now,</span> <span m="2148520">the</span> <span m="2148630">good</span> <span m="2148780">news</span> <span m="2148980">is</span> <span m="2149100">that</span> <span m="2149370">axioms</span> <span m="2149880">are</span> <span m="2149920">the</span> <span m="2150030">same</span> <span m="2150370">thing,</span> <span m="2150660">really,</span> <span m="2150920">as</span> <span m="2151030">propositions.</span> <span m="2152920">The</span> <span m="2153060">only</span> <span m="2153250">difference</span> <span m="2153710">is</span> <span m="2153950">that</span> <span m="2154080">axioms</span> <span m="2155210">are</span> <span m="2155370">propositions</span> <span m="2156130">that</span> <span m="2156230">we</span> <span m="2156350">just</span> <span m="2156600">assume</span> <span m="2157070">are</span> <span m="2157130">true.</span> <span m="2161930">An</span> <span m="2162080">axiom</span> <span m="2164140">is</span> <span m="2164370">a</span> <span m="2164440">proposition</span> <span m="2170290">that</span> <span m="2170670">is</span> <span m="2171240">assumed</span> <span m="2175570">to</span> <span m="2175910">be</span> <span m="2176040">true.</span> </p>
<p><span m="2180130">There's</span> <span m="2180230">no</span> <span m="2180460">proof</span> <span m="2181510">that</span> <span m="2181610">an</span> <span m="2181700">axiom</span> <span m="2182060">is</span> <span m="2182170">true.</span> <span m="2183570">You</span> <span m="2183700">just</span> <span m="2183920">assume</span> <span m="2184290">it</span> <span m="2184380">because</span> <span m="2184600">you</span> <span m="2184810">think</span> <span m="2185050">it's</span> <span m="2185180">reasonable.</span> <span m="2186740">In</span> <span m="2186840">fact,</span> <span m="2187060">the</span> <span m="2187160">word</span> <span m="2187520">"axiom"</span> <span m="2188040">comes</span> <span m="2188380">from</span> <span m="2188550">Greek.</span> <span m="2189430">It</span> <span m="2189560">doesn't</span> <span m="2189880">mean</span> <span m="2191430">to</span> <span m="2191550">be</span> <span m="2191660">true.</span> <span m="2192250">It</span> <span m="2192390">means</span> <span m="2192710">to</span> <span m="2192820">think</span> <span m="2193150">worthy--</span> <span m="2194890">something</span> <span m="2195180">you</span> <span m="2195290">think</span> <span m="2195510">is</span> <span m="2195610">worthy</span> <span m="2196000">enough</span> <span m="2196200">to</span> <span m="2196300">be</span> <span m="2196400">assumed</span> <span m="2196810">to</span> <span m="2196860">be</span> <span m="2196970">true.</span> </p>
<p><span m="2197950">Now,</span> <span m="2198190">a</span> <span m="2198260">lot</span> <span m="2198460">of</span> <span m="2198520">times,</span> <span m="2198790">you'll</span> <span m="2199040">hear</span> <span m="2199170">people</span> <span m="2199470">say--</span> <span m="2200280">sometimes,</span> <span m="2200610">we'll</span> <span m="2200780">even</span> <span m="2200960">say</span> <span m="2201210">it</span> <span m="2201320">to</span> <span m="2201430">you--</span> <span m="2202980">don't</span> <span m="2203280">make</span> <span m="2203490">assumptions</span> <span m="2204000">when</span> <span m="2204090">you're</span> <span m="2204170">doing</span> <span m="2204420">math.</span> <span m="2206150">No,</span> <span m="2206380">that's</span> <span m="2206590">not</span> <span m="2206900">true.</span> <span m="2207960">You</span> <span m="2208060">have</span> <span m="2208280">to</span> <span m="2208380">make</span> <span m="2208550">assumptions</span> <span m="2208990">when</span> <span m="2209080">you</span> <span m="2209170">do</span> <span m="2209320">math.</span> <span m="2209690">Otherwise,</span> <span m="2210080">you</span> <span m="2210180">can't</span> <span m="2210410">do</span> <span m="2210550">anything</span> <span m="2211330">because</span> <span m="2211500">you</span> <span m="2211570">have</span> <span m="2211680">to</span> <span m="2211750">start</span> <span m="2212120">with</span> <span m="2212220">some</span> <span m="2212370">axioms.</span> </p>
<p><span m="2213900">The</span> <span m="2214020">key</span> <span m="2214290">in</span> <span m="2214380">math</span> <span m="2214890">is</span> <span m="2216050">to</span> <span m="2216380">identify</span> <span m="2217040">what</span> <span m="2217210">your</span> <span m="2217390">assumptions</span> <span m="2217920">are</span> <span m="2218240">so</span> <span m="2218370">people</span> <span m="2218660">can</span> <span m="2218870">see</span> <span m="2219050">them.</span> <span m="2220450">And</span> <span m="2220540">the</span> <span m="2220680">idea</span> <span m="2221160">is</span> <span m="2221560">that</span> <span m="2221800">when</span> <span m="2221890">you</span> <span m="2221990">do</span> <span m="2222110">a</span> <span m="2222180">proof,</span> <span m="2223350">anybody</span> <span m="2223710">who</span> <span m="2223840">agrees</span> <span m="2224300">with</span> <span m="2224440">your</span> <span m="2224560">assumptions</span> <span m="2224900">or</span> <span m="2225240">your</span> <span m="2225310">axioms</span> <span m="2226690">can</span> <span m="2226820">follow</span> <span m="2227100">your</span> <span m="2227250">proof.</span> <span m="2227550">And</span> <span m="2227640">they</span> <span m="2227750">have</span> <span m="2228060">to</span> <span m="2228190">agree</span> <span m="2228440">with</span> <span m="2228570">your</span> <span m="2228690">conclusion.</span> <span m="2229660">Now,</span> <span m="2230140">they</span> <span m="2230210">might</span> <span m="2230550">disagree</span> <span m="2231440">with</span> <span m="2231590">your</span> <span m="2231720">axioms,</span> <span m="2232210">in</span> <span m="2232290">which</span> <span m="2232450">case,</span> <span m="2232680">they're</span> <span m="2232770">not</span> <span m="2232960">going</span> <span m="2233060">to</span> <span m="2233330">buy</span> <span m="2233660">your</span> <span m="2234320">proof.</span> </p>
<p><span m="2235810">Now,</span> <span m="2235930">there</span> <span m="2236070">are</span> <span m="2236130">lots</span> <span m="2236540">of</span> <span m="2236640">axioms</span> <span m="2237150">used</span> <span m="2237440">in</span> <span m="2237520">math.</span> <span m="2239020">For</span> <span m="2239180">example,</span> <span m="2242750">if</span> <span m="2243080">a</span> <span m="2243440">equals</span> <span m="2243910">b</span> <span m="2245260">and</span> <span m="2245610">b</span> <span m="2246110">equals</span> <span m="2246500">c,</span> <span m="2248080">then</span> <span m="2249050">a</span> <span m="2249520">equals</span> <span m="2249890">c.</span> <span m="2251670">There</span> <span m="2251870">is</span> <span m="2252040">no</span> <span m="2252250">proof</span> <span m="2252550">of</span> <span m="2252660">that.</span> <span m="2254250">But</span> <span m="2254380">it</span> <span m="2254510">seems</span> <span m="2254980">pretty</span> <span m="2255200">good.</span> <span m="2256090">And</span> <span m="2256260">so</span> <span m="2256370">we</span> <span m="2256480">just</span> <span m="2257130">throw</span> <span m="2257560">it</span> <span m="2257610">in</span> <span m="2257680">the</span> <span m="2257750">bucket</span> <span m="2258070">of</span> <span m="2258160">axioms</span> <span m="2258840">and</span> <span m="2259080">use</span> <span m="2259370">it.</span> </p>
<p><span m="2261580">Now,</span> <span m="2263040">axioms</span> <span m="2263690">can</span> <span m="2263840">be</span> <span m="2263990">contradictory</span> <span m="2264920">in</span> <span m="2265070">different</span> <span m="2265890">contexts.</span> <span m="2267210">Here's</span> <span m="2267420">a</span> <span m="2267750">good</span> <span m="2267920">example.</span> <span m="2269340">In</span> <span m="2269640">Euclidean</span> <span m="2270190">geometry,</span> <span m="2274860">there's</span> <span m="2275050">a</span> <span m="2275120">central</span> <span m="2275620">axiom</span> <span m="2276090">that</span> <span m="2276220">says</span> <span m="2277890">given</span> <span m="2280090">a</span> <span m="2280230">line</span> <span m="2282290">L</span> <span m="2283470">and</span> <span m="2283900">a</span> <span m="2284080">point</span> <span m="2286010">p</span> <span m="2287210">not</span> <span m="2287390">on</span> <span m="2287837">L,</span> <span m="2291420">there is</span> <span m="2292820">exactly</span> <span m="2293360">one</span> <span m="2298340">line</span> <span m="2300330">through</span> <span m="2301360">p</span> <span m="2301690">parallel</span> <span m="2302090">to</span> <span m="2302180">L.</span> <span m="2308450">You</span> <span m="2308590">all</span> <span m="2308830">saw</span> <span m="2309120">this</span> <span m="2309390">in</span> <span m="2309560">geometry</span> <span m="2310680">in</span> <span m="2310810">middle</span> <span m="2311020">school,</span> <span m="2311280">right?</span> <span m="2312020">You've got</span> <span m="2312150">a</span> <span m="2312200">point</span> <span m="2312500">in a line.</span> <span m="2312920">There's</span> <span m="2313060">exactly</span> <span m="2314350">another</span> <span m="2314460">line</span> <span m="2314710">through</span> <span m="2314780">the</span> <span m="2314870">point</span> <span m="2315160">that's</span> <span m="2315280">parallel</span> <span m="2315690">to the</span> <span m="2315850">line.</span> </p>
<p><span m="2318220">Now,</span> <span m="2318460">there's</span> <span m="2318650">also</span> <span m="2319100">a</span> <span m="2319150">field</span> <span m="2319520">called</span> <span m="2319800">spherical</span> <span m="2320300">geometry.</span> <span m="2324870">And</span> <span m="2325010">there,</span> <span m="2325190">you</span> <span m="2325270">have</span> <span m="2325460">an</span> <span m="2325550">axiom</span> <span m="2326960">that</span> <span m="2327080">contradicts</span> <span m="2327340">this.</span> <span m="2327820">It</span> <span m="2327930">says,</span> <span m="2328820">given</span> <span m="2328940">a</span> <span m="2329010">line</span> <span m="2329370">L</span> <span m="2329710">and</span> <span m="2329780">a</span> <span m="2329840">point</span> <span m="2330230">p</span> <span m="2330820">not on</span> <span m="2330990">L,</span> <span m="2332220">there</span> <span m="2332630">is</span> <span m="2333270">no</span> <span m="2335630">line</span> <span m="2336810">through</span> <span m="2337090">p</span> <span m="2337420">parallel</span> <span m="2337830">to</span> <span m="2337930">L</span> <span m="2338922">on</span> <span m="2339420">the</span> <span m="2339490">sphere.</span> <span m="2341840">There's</span> <span m="2342030">a</span> <span m="2342090">field</span> <span m="2342420">called</span> <span m="2343960">hyperbolic</span> <span m="2346520">geometry.</span> <span m="2349270">And</span> <span m="2349440">there,</span> <span m="2350050">there's</span> <span m="2350220">an</span> <span m="2350290">axiom</span> <span m="2350630">that</span> <span m="2350720">says,</span> <span m="2351190">given</span> <span m="2351320">a</span> <span m="2351380">line</span> <span m="2351730">L and a</span> <span m="2352150">point</span> <span m="2352440">p not</span> <span m="2352750">on</span> <span m="2352860">L,</span> <span m="2353800">there</span> <span m="2354340">are</span> <span m="2355990">infinitely</span> <span m="2356690">many</span> <span m="2362690">lines</span> <span m="2363710">through</span> <span m="2363980">p</span> <span m="2364330">parallel</span> <span m="2364750">to</span> <span m="2364840">L.</span> </p>
<p><span m="2366632">So how</span> <span m="2367080">can</span> <span m="2367200">this</span> <span m="2367400">be?</span> <span m="2367690">Does that</span> <span m="2367860">mean</span> <span m="2368080">one</span> <span m="2368200">of</span> <span m="2368240">these</span> <span m="2368460">fields</span> <span m="2368820">is</span> <span m="2368920">totally</span> <span m="2369310">bogus,</span> <span m="2369870">or</span> <span m="2369970">two</span> <span m="2370150">of</span> <span m="2370230">them</span> <span m="2370390">are?</span> <span m="2371620">Because</span> <span m="2371780">they've</span> <span m="2371860">got</span> <span m="2372070">contradictory</span> <span m="2372840">axes.</span> </p>
<p><span m="2374470">That's</span> <span m="2374690">OK.</span> <span m="2375860">Just</span> <span m="2376050">whatever</span> <span m="2376320">field</span> <span m="2376660">you're</span> <span m="2376840">in,</span> <span m="2377180">state</span> <span m="2377450">you're</span> <span m="2377630">axioms.</span> <span m="2379230">And</span> <span m="2379330">they</span> <span m="2379430">do</span> <span m="2379610">make</span> <span m="2379830">sense</span> <span m="2380700">in</span> <span m="2380810">their</span> <span m="2380930">various</span> <span m="2381310">fields.</span> <span m="2382610">This</span> <span m="2382900">is</span> <span m="2383000">planar</span> <span m="2383330">geometry.</span> <span m="2383810">This</span> <span m="2383980">is</span> <span m="2384090">on</span> <span m="2384210">the</span> <span m="2384270">sphere.</span> <span m="2384710">And this</span> <span m="2384930">is</span> <span m="2385030">on</span> <span m="2386390">hyperbolic</span> <span m="2386930">geometry.</span> <span m="2387880">They</span> <span m="2387970">make</span> <span m="2388200">sense</span> <span m="2388460">in</span> <span m="2388510">those</span> <span m="2388670">contexts.</span> </p>
<p><span m="2389990">So</span> <span m="2390710">you</span> <span m="2390870">can</span> <span m="2390990">have</span> <span m="2392130">more</span> <span m="2392350">or less</span> <span m="2392460">whatever</span> <span m="2393460">axioms</span> <span m="2393810">you</span> <span m="2393910">want.</span> <span m="2394750">There</span> <span m="2394940">are</span> <span m="2395100">sort</span> <span m="2395280">of</span> <span m="2395390">two</span> <span m="2395660">guiding</span> <span m="2396050">principles</span> <span m="2396640">to</span> <span m="2396740">axioms.</span> <span m="2415440">Axioms</span> <span m="2415950">should</span> <span m="2416190">be--</span> <span m="2417250">it's</span> <span m="2417480">called</span> <span m="2417930">consistent--</span> <span m="2420920">and</span> <span m="2422040">complete.</span> <span m="2425890">Now,</span> <span m="2428580">a</span> <span m="2428650">set</span> <span m="2428850">of</span> <span m="2428940">axioms</span> <span m="2434050">is</span> <span m="2434300">consistent</span> <span m="2439880">if</span> <span m="2440250">no</span> <span m="2440600">proposition</span> <span m="2445660">can</span> <span m="2446160">be</span> <span m="2446320">proved</span> <span m="2446890">to</span> <span m="2446980">be</span> <span m="2447110">both</span> <span m="2447520">true</span> <span m="2447760">and</span> <span m="2447860">false.</span> </p>
<p><span m="2455190">And</span> <span m="2455350">you</span> <span m="2455440">can</span> <span m="2455550">see</span> <span m="2455740">why</span> <span m="2455910">that's</span> <span m="2456150">important.</span> <span m="2457640">If</span> <span m="2457710">you</span> <span m="2457820">spend</span> <span m="2458720">three</span> <span m="2458980">weeks</span> <span m="2460150">proving</span> <span m="2460410">something's</span> <span m="2460780">true,</span> <span m="2462120">and</span> <span m="2462150">the</span> <span m="2462220">next</span> <span m="2462450">day,</span> <span m="2462730">somebody</span> <span m="2463010">proves</span> <span m="2463310">it's</span> <span m="2463440">also</span> <span m="2464030">false,</span> <span m="2464880">I mean,</span> <span m="2465000">the</span> <span m="2465100">whole</span> <span m="2465260">thing</span> <span m="2465440">was</span> <span m="2465740">pointless.</span> <span m="2467020">So</span> <span m="2467230">it</span> <span m="2467300">only</span> <span m="2467490">makes</span> <span m="2467740">sense</span> <span m="2468010">if</span> <span m="2468100">your</span> <span m="2468260">axioms,</span> <span m="2468680">as</span> <span m="2468800">a</span> <span m="2468860">group,</span> <span m="2469630">are</span> <span m="2469770">consistent.</span> </p>
<p><span m="2472140">A</span> <span m="2472350">set</span> <span m="2472530">of</span> <span m="2472610">axioms</span> <span m="2473030">is</span> <span m="2473130">said</span> <span m="2473320">to</span> <span m="2473380">be</span> <span m="2473500">complete</span> <span m="2486610">if</span> <span m="2486930">it</span> <span m="2487350">can</span> <span m="2487500">be</span> <span m="2487650">used</span> <span m="2491880">to</span> <span m="2492110">prove</span> <span m="2494430">every</span> <span m="2494840">proposition</span> <span m="2495550">is</span> <span m="2495800">either</span> <span m="2496250">true</span> <span m="2496500">or</span> <span m="2496570">false.</span> <span m="2508560">Now,</span> <span m="2508810">this</span> <span m="2509085">is</span> <span m="2509360">desirable</span> <span m="2509720">because</span> <span m="2510030">it</span> <span m="2510140">means--</span> <span m="2511710">well,</span> <span m="2511930">you</span> <span m="2512030">can</span> <span m="2512190">solve</span> <span m="2512420">every</span> <span m="2512620">problem.</span> <span m="2514450">Everything</span> <span m="2514780">is--</span> <span m="2515770">you</span> <span m="2515910">can</span> <span m="2516090">prove</span> <span m="2516290">it's true,</span> <span m="2516660">or you</span> <span m="2516720">can</span> <span m="2516840">prove</span> <span m="2517050">it's</span> <span m="2517170">false.</span> <span m="2517480">You</span> <span m="2517580">can</span> <span m="2517750">get</span> <span m="2517940">to</span> <span m="2519010">the</span> <span m="2519170">end.</span> </p>
<p><span m="2520010">Now,</span> <span m="2524040">you'd</span> <span m="2524350">think</span> <span m="2524620">it</span> <span m="2524730">shouldn't</span> <span m="2525000">be</span> <span m="2525110">too</span> <span m="2525280">hard</span> <span m="2525760">to</span> <span m="2525840">get</span> <span m="2526000">a</span> <span m="2526060">set</span> <span m="2526260">of</span> <span m="2526360">axioms</span> <span m="2526950">that</span> <span m="2527110">satisfies</span> <span m="2527830">these</span> <span m="2528050">two</span> <span m="2528230">basic</span> <span m="2528610">properties.</span> <span m="2529730">You're</span> <span m="2529900">allowed</span> <span m="2530250">to</span> <span m="2530330">choose</span> <span m="2530660">whatever</span> <span m="2530990">you</span> <span m="2531120">want,</span> <span m="2531590">really.</span> <span m="2532490">Just,</span> <span m="2532770">you</span> <span m="2532860">don't</span> <span m="2533160">want</span> <span m="2533320">to</span> <span m="2533600">be</span> <span m="2533760">creating</span> <span m="2534080">contradictions.</span> <span m="2534990">And</span> <span m="2535420">you want</span> <span m="2535610">a</span> <span m="2535840">set</span> <span m="2536060">that's</span> <span m="2536220">powerful</span> <span m="2536690">enough</span> <span m="2536920">that allows</span> <span m="2537270">you</span> <span m="2537340">to</span> <span m="2537410">prove</span> <span m="2537700">everything</span> <span m="2538030">is</span> <span m="2538120">true</span> <span m="2538430">or</span> <span m="2538540">false,</span> <span m="2538970">one of</span> <span m="2539150">the</span> <span m="2539270">two.</span> </p>
<p><span m="2540740">Turned</span> <span m="2540980">out</span> <span m="2541080">not</span> <span m="2541300">to</span> <span m="2541360">be</span> <span m="2541460">so</span> <span m="2541660">easy</span> <span m="2541970">to</span> <span m="2542030">do</span> <span m="2542250">this.</span> <span m="2543350">And in</span> <span m="2543540">fact,</span> <span m="2544840">many</span> <span m="2545180">logicians</span> <span m="2545760">spent</span> <span m="2546120">their</span> <span m="2546240">careers--</span> <span m="2547800">famous</span> <span m="2548210">logicians--</span> <span m="2548700">trying</span> <span m="2549260">to</span> <span m="2549330">find</span> <span m="2549700">a</span> <span m="2549750">set</span> <span m="2549940">of</span> <span m="2550040">axioms,</span> <span m="2550760">just</span> <span m="2550980">one</span> <span m="2551220">set,</span> <span m="2552030">that</span> <span m="2552130">was</span> <span m="2552660">consistent</span> <span m="2553370">and</span> <span m="2553910">complete.</span> <span m="2555000">In fact,</span> <span m="2555180">Russell</span> <span m="2555540">and</span> <span m="2555620">Whitehead</span> <span m="2556020">are</span> <span m="2556080">probably</span> <span m="2556320">the</span> <span m="2556420">two</span> <span m="2556580">most</span> <span m="2556870">famous.</span> <span m="2557820">They</span> <span m="2557920">spent</span> <span m="2558130">their</span> <span m="2558240">entire</span> <span m="2558570">careers</span> <span m="2559530">doing</span> <span m="2559800">this,</span> <span m="2560080">and</span> <span m="2560200">they</span> <span m="2560580">never</span> <span m="2560820">got</span> <span m="2561040">there.</span> </p>
<p><span m="2562270">Then</span> <span m="2562490">one</span> <span m="2562710">day,</span> <span m="2562870">this</span> <span m="2563070">guy</span> <span m="2563230">named</span> <span m="2563450">Kurt</span> <span m="2563750">Godel</span> <span m="2564080">showed</span> <span m="2564340">up.</span> <span m="2565570">And</span> <span m="2565920">in</span> <span m="2565990">the</span> <span m="2566050">1930s,</span> <span m="2567820">he</span> <span m="2568060">proved</span> <span m="2568330">it's</span> <span m="2568470">not</span> <span m="2568790">possible</span> <span m="2569940">that</span> <span m="2570100">there</span> <span m="2570260">exists</span> <span m="2570790">any</span> <span m="2571020">set</span> <span m="2571210">of</span> <span m="2571300">axioms</span> <span m="2571645">that</span> <span m="2571990">are</span> <span m="2572060">both</span> <span m="2573270">consistent</span> <span m="2574320">and</span> <span m="2574550">complete.</span> <span m="2576450">Now,</span> <span m="2576580">this</span> <span m="2576820">discovery</span> <span m="2577410">devastated</span> <span m="2578710">the</span> <span m="2578810">field.</span> <span m="2579560">It was</span> <span m="2579740">a</span> <span m="2579980">huge</span> <span m="2580520">discovery.</span> </p>
<p><span m="2582270">Imagine</span> <span m="2582890">poor</span> <span m="2583210">Russell and</span> <span m="2583530">Whitehead.</span> <span m="2584670">They</span> <span m="2584780">spent</span> <span m="2584960">their</span> <span m="2585080">entire</span> <span m="2585480">careers</span> <span m="2586420">going</span> <span m="2586640">after</span> <span m="2586850">this</span> <span m="2586980">holy</span> <span m="2587230">grail.</span> <span m="2588180">Then</span> <span m="2588350">Kurt</span> <span m="2588590">shows</span> <span m="2588860">up</span> <span m="2588990">and</span> <span m="2589110">said,</span> <span m="2589280">hey,</span> <span m="2589430">guys.</span> <span m="2589660">There's</span> <span m="2589820">no</span> <span m="2589960">grail.</span> <span m="2590580">It</span> <span m="2590850">doesn't</span> <span m="2591100">exist.</span> <span m="2591910">And</span> <span m="2592240">that's</span> <span m="2592360">a</span> <span m="2592420">little</span> <span m="2593120">depressing--</span> <span m="2593850">pretty</span> <span m="2594100">bad</span> <span m="2594370">day</span> <span m="2594580">when</span> <span m="2594690">that</span> <span m="2594830">happened.</span> </p>
<p><span m="2595840">Now,</span> <span m="2596620">it's</span> <span m="2596780">an</span> <span m="2596860">amazing</span> <span m="2597270">result,</span> <span m="2597640">because</span> <span m="2597900">it</span> <span m="2598000">says</span> <span m="2598220">if</span> <span m="2598310">you</span> <span m="2598440">want</span> <span m="2598780">consistency--</span> <span m="2599720">and</span> <span m="2599780">that's</span> <span m="2599980">a</span> <span m="2600030">must--</span> <span m="2601600">there</span> <span m="2601760">will</span> <span m="2602080">be</span> <span m="2602220">true</span> <span m="2602660">facts</span> <span m="2603630">that</span> <span m="2603780">you</span> <span m="2603910">will</span> <span m="2604080">never</span> <span m="2604630">be</span> <span m="2604880">able</span> <span m="2605020">to</span> <span m="2605100">prove.</span> <span m="2606590">We're</span> <span m="2606720">not</span> <span m="2606850">going</span> <span m="2606930">to</span> <span m="2606980">prove</span> <span m="2607190">that</span> <span m="2607340">here.</span> <span m="2607510">It's</span> <span m="2607570">proved</span> <span m="2607740">in a</span> <span m="2607870">logic</span> <span m="2608190">course.</span> <span m="2609210">For</span> <span m="2609340">example,</span> <span m="2609760">maybe</span> <span m="2610120">Goldbach's</span> <span m="2610640">conjecture</span> <span m="2611200">is</span> <span m="2611370">true</span> <span m="2612740">and</span> <span m="2613010">it</span> <span m="2613070">is</span> <span m="2613230">impossible</span> <span m="2613515">to</span> <span m="2613800">prove.</span> </p>
<p><span m="2615960">Now,</span> <span m="2616160">we're</span> <span m="2616410">going</span> <span m="2616510">to</span> <span m="2616580">try</span> <span m="2616840">not</span> <span m="2617180">to</span> <span m="2617260">assign</span> <span m="2617630">any</span> <span m="2617810">of</span> <span m="2617860">those</span> <span m="2618060">problems</span> <span m="2618420">for</span> <span m="2618530">homework.</span> <span m="2620210">And</span> <span m="2620320">in</span> <span m="2620390">fact,</span> <span m="2621050">they</span> <span m="2621200">do</span> <span m="2621390">exist.</span> <span m="2622260">It's</span> <span m="2622600">complicated.</span> <span m="2622890">You can</span> <span m="2623180">state a</span> <span m="2623540">problem</span> <span m="2624610">that</span> <span m="2624740">you</span> <span m="2624860">can't</span> <span m="2625240">prove</span> <span m="2625610">is</span> <span m="2625710">true</span> <span m="2625880">or</span> <span m="2625980">false.</span> </p>
<p><span m="2627690">And</span> <span m="2627770">you</span> <span m="2627850">may</span> <span m="2627970">be</span> <span m="2628110">thinking</span> <span m="2628510">that</span> <span m="2628680">from</span> <span m="2628810">time</span> <span m="2629060">to</span> <span m="2629140">time.</span> <span m="2629390">Hey, it's</span> <span m="2629690">one</span> <span m="2629860">of</span> <span m="2629920">those.</span> <span m="2633500">Remember</span> <span m="2633710">when</span> <span m="2633760">your</span> <span m="2633890">parents</span> <span m="2634290">told</span> <span m="2634590">you</span> <span m="2635430">if</span> <span m="2635580">you</span> <span m="2635700">work</span> <span m="2635920">hard</span> <span m="2636190">enough,</span> <span m="2637140">you</span> <span m="2637280">can</span> <span m="2637420">do</span> <span m="2637570">anything?</span> <span m="2639270">They</span> <span m="2639470">were</span> <span m="2639590">wrong.</span> </p>
<p><span m="2641890">All</span> <span m="2642170">right,</span> <span m="2642420">that's</span> <span m="2642620">enough</span> <span m="2642870">for</span> <span m="2642990">now.</span> <span m="2643270">And we'll</span> <span m="2643660">do</span> <span m="2643780">more of</span> <span m="2643970">this</span> <span m="2644170">next</span> <span m="2644470">time.</span> </p>
</div>
        <div id="vid_related" itemprop="description" class="tabContent hide">
<h2 class="subhead">Free Downloads</h2>
<h3 class="subsubhead">Video</h3>
<ul>
<li>iTunes U (<a href="http://itunes.apple.com/us/itunes-u/lecture-1-introduction-proofs/id503873536?i=110644965">MP4 - 96MB</a>)</li>
<li>Internet Archive (<a href="http://www.archive.org/download/MIT6.042JF10/MIT6_042JF10_lec01_300k.mp4">MP4 - 96MB</a>)</li>
</ul>
<br>
<h3 class="subsubhead">Caption</h3>
<ul>
<li>English-US (<a href="../../../contents/video-lectures/lecture-1-introduction-and-proofs/L3LMbpZIKhQ.srt">SRT</a>)</li>
</ul>
</div>
    
   </div>  




      					 
        <div class="" id="parent-fieldname-bottom_html_area">
            
            
        </div>
    
               </main><!--Course_inner_media tag close -->
           		</div>
<!--Course_wrapper tag close -->
            </div>
<!--left tag close -->
            <aside id="right">
                <!--Begin Right Portion -->
                    <div>
    



</div>

                	<div>
    



</div>


        <div class="" id="parent-fieldname-rsi_top_html_area">
            
            
        </div>
    

<!-- RSI google ad space-->



<div id="google_ads">    
    <script async="async" src="https://www.googletagservices.com/tag/js/gpt.js"></script>
    <script type="text/javascript">var googletag = googletag || {}; googletag.cmd = googletag.cmd || [];</script>
    <script type="text/javascript">
googletag.cmd.push(function() {googletag.defineSlot('/1064917/VIDEO_INDIVIDUAL_SLOT_A_DL', [[300, 250], [300, 300], [180, 200], [180, 150], [160, 600]], 'VIDEO_INDIVIDUAL_SLOT_A_DL').addService(googletag.pubads());googletag.defineSlot('/1064917/VIDEO_INDIVIDUAL_SLOT_B_DL', [[300, 250], [300, 300], [180, 200], [180, 150], [160, 600]], 'VIDEO_INDIVIDUAL_SLOT_B_DL').addService(googletag.pubads());googletag.defineSlot('/1064917/VIDEO_INDIVIDUAL_SLOT_C_DL', [[300, 250], [300, 300], [180, 200], [180, 150], [160, 600]], 'VIDEO_INDIVIDUAL_SLOT_C_DL').addService(googletag.pubads());
googletag.pubads().enableSingleRequest();
 googletag.enableServices();
});</script>
    <script language="javascript" type="text/javascript">
googletag.cmd.push(function() {googletag.pubads().set("TYPE","HOUSE");googletag.pubads().set("DEPARTMENT","6");googletag.pubads().set("CRS_BEG2","04");googletag.pubads().set("CRS_END","2J");googletag.pubads().set("SESSION","F");googletag.pubads().set("YEAR","10");})
</script>
    
    <div id="VIDEO_INDIVIDUAL_SLOT_A_DL">
    	<script>googletag.cmd.push(function() { googletag.display('VIDEO_INDIVIDUAL_SLOT_A_DL'); });</script>
    </div>
    <div id="VIDEO_INDIVIDUAL_SLOT_B_DL">
    	<script>googletag.cmd.push(function() { googletag.display('VIDEO_INDIVIDUAL_SLOT_B_DL'); });</script>
    </div>
    <div id="VIDEO_INDIVIDUAL_SLOT_C_DL">
    	<script>googletag.cmd.push(function() { googletag.display('VIDEO_INDIVIDUAL_SLOT_C_DL'); });</script>
    </div>
</div>

<!-- End RSI ads--> 


<div>
    



</div>

            </aside><!--Right div close -->
            <div class="clear"></div>
        </div>
<!--grid tag close -->
      </div>
		
		<footer id="bottom">
			<div id="grid">
				
<div id="portletwrapper-6f63772e626f74746f6d706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d666f6f746572" class="portletWrapper kssattr-portlethash-6f63772e626f74746f6d706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d666f6f746572">
<div class="portletStaticText portlet-static-site-footer"><div id="footer">
<nav aria-label="Footer">     <nav id="foot-c1" class="grid_2 alpha" aria-labelledby="f-find-courses">       <span class="footer" id="f-find-courses" aria-hidden="true">Find Courses</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/courses/find-by-topic/">Find by Topic</a></li>
    <li><a href="https://ocw.mit.edu/courses/find-by-number/">Find by Course Number</a></li>
    <li><a href="https://ocw.mit.edu/courses/find-by-department/">Find by Department</a></li>
    <li><a href="https://ocw.mit.edu/courses/new-courses/">New Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/most-visited-courses/">Most Visited Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/ocw-scholar/">OCW Scholar Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/audio-video-courses/">Audio/Video Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/online-textbooks/">Online Textbooks</a></li>
    <li><a href="https://ocw.mit.edu/courses/instructor-insights/">Instructor Insights</a></li>
    <li><a href="https://ocw.mit.edu/resources/">Supplemental Resources</a></li>
    <li><a href="https://ocw.mit.edu/courses/mitx-related-courseware/">MITx &amp; Related OCW Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/mit-open-learning-library/">MIT Open Learning Library</a></li>
    <li><a href="https://ocw.mit.edu/courses/translated-courses/">Translated Courses</a></li>
</ul>
</nav>
<div id="foot-c2" class="grid_2"><nav aria-labelledby="f-for-educators">         <span id="f-for-educators" class="footer" aria-hidden="true">For Educators</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://chalk-radio.simplecast.com/">Chalk Radio Podcast</a></li>
    <li><a href="https://ocw.mit.edu/educator/">OCW Educator Portal </a></li>
    <li><a href="https://ocw.mit.edu/courses/instructor-insights/">Instructor Insights by Department</a></li>
    <li><a href="https://openlearning.mit.edu/campus/digital-innovations/" aria-label="External Link: Residential Digital Innovations">Residential Digital Innovations </a></li>
    <li><a href="https://ocw.mit.edu/high-school/">OCW Highlights for High School</a></li>
    <li><a href="https://ocw.mit.edu/educator/additional-resources/">Additional Resources</a></li>
</ul>
</nav></div>
<nav class="grid_2" id="foot-c3" aria-labelledby="f-donate">       <span id="f-donate" class="footer" aria-hidden="true">Give Now</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/give/">Make a Donation</a></li>
    <li><a href="https://ocw.mit.edu/give/why-give/">Why Give?</a></li>
    <li><a href="https://ocw.mit.edu/give/our-supporters/">Our Supporters</a></li>
    <li><a href="https://ocw.mit.edu/give/other-ways-to-contribute/">Other Ways to Contribute</a></li>
    <li><a href="https://ocw.mit.edu/support/">Become a Corporate Sponsor</a></li>
</ul>
</nav>
<div class="grid_2" id="foot-c4">
<nav aria-labelledby="f-about">         <span id="f-about" class="footer" aria-hidden="true">About</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/about/">About OpenCourseWare</a></li>
    <li><a href="https://ocw.mit.edu/about/site-statistics/">Site Statistics</a></li>
    <li><a href="https://ocw.mit.edu/about/ocw-stories/">OCW Stories</a></li>
    <li><a href="https://ocw.mit.edu/about/newsletter/">Newsletter</a></li>
    <li><a href="https://www.ocw-openmatters.org/">Open Matters Blog</a></li>
</ul>
</nav><!--about-->       <nav aria-labelledby="f-tools">         <span id="f-tools" class="footer" aria-hidden="true">Tools</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/help/">Help &amp; FAQs</a></li>
    <li><a href="https://ocw.mit.edu/about/contactus">Contact Us</a></li>
    <li><a href="https://accessibility.mit.edu/" target="_blank">Accessibility</a></li>
    <li><a href="https://ocw.mit.edu/help/site-map/">Site Map</a></li>
    <li><a href="../../../common/terms/index.htm">Privacy &amp; Terms of Use</a></li>
    <li><a href="https://ocw.mit.edu/help/rss/">RSS Feeds</a></li>
</ul>
</nav><!--tools-->
</div>
</nav> <aside style="min-height: 289px;" aria-labelledby="f-our-corporate-supporters" class="grid_4 omega" id="foot-c5">           <span aria-hidden="true" class="footer" id="f-our-corporate-supporters">Our Corporate Supporters</span>           <!-- HOME_CORP_LOGO_1 -->
<div id="div-gpt-ad-1388181177156-0" class="sponsors_google_ads_even"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-0'); });
            </script></div>
<!-- HOME_CORP_LOGO_2 -->
<div id="div-gpt-ad-1388181177156-1" class="sponsors_google_ads_odd"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-1'); });
            </script></div>
<!-- HOME_CORP_LOGO_3 -->
<div id="div-gpt-ad-1388181177156-2" class="sponsors_google_ads_even"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-2'); });
            </script></div>
<!-- HOME_CORP_LOGO_4 -->
<div id="div-gpt-ad-1388181177156-3" class="sponsors_google_ads_odd"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-3'); });
            </script></div>
<!-- HOME_CORP_LOGO_5 -->
<div id="div-gpt-ad-1388181177156-4" class="sponsors_google_ads_even"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-4'); });
              </script></div>
<!-- HOME_CORP_LOGO_6 -->
<div id="div-gpt-ad-1388181177156-5" class="sponsors_google_ads_odd"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-5'); });
              </script></div>
</aside>
<div class="grid_12 alpha omega" itemprop="publisher" itemscope="" itemtype="http://schema.org/CollegeOrUniversity">
<h4 class="footer" style="border-top: thin solid #d5c9ba; padding-top: 10px; margin-bottom: 10px;">About <span itemprop="name">MIT OpenCourseWare</span>
</h4>
<p style="color: #999; font-size: 1em; line-height: 1.5em; margin-top: 10px;" itemprop="description">MIT OpenCourseWare is an online publication of materials from over 2,500 MIT courses, freely sharing knowledge with learners and educators around the world. <a href="https://ocw.mit.edu/about/">Learn more »</a></p>
</div>
<div id="foot-copy" class="grid_12 alpha omega" style="border-top: none;">
<a href="http://web.mit.edu"><img src="../../../common/images/logo_mit.png" alt="Massachusetts Institute of Technology logo and name." style="width: 195; height: 44;"></a><a href="https://openlearning.mit.edu/"><img src="https://ocw.mit.edu/images/mitol_logo.png" alt="MIT Open Learning logo and name." style="width: 265; height: 50; vertical-align: top; padding-left:30px;"></a><a href="https://www.oeglobal.org/"><img src="https://ocw.mit.edu/images/oeg_logo.gif" alt="Open Education Consortium logo." style="width: 219px; height: 59px; vertical-align: top; padding-left:20px;"></a><a rel="license" itemprop="useRightsUrl" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="../../../common/images/cc_by-nc-sa.png" alt="Creative Commons logo with terms BY-NC-SA." style="width: 126px; height: 44px; margin-right: 0; padding-left: 20px;"></a>
<p class="copyright">© 2001–2018<br>
Massachusetts Institute of Technology</p>
<p style="font-size: 0.9em; margin-bottom: 15px;">Your use of the MIT OpenCourseWare site and materials is subject to our <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="license">Creative Commons License</a> and other <a href="../../../common/terms/index.htm" rel="cc:morePermissions">terms of use</a>.</p>
</div>
</div></div>

</div>





                
			</div> <!-- bottom grid end -->
		</footer><!-- footer bottom end -->


   </body>
 </html>
